Paul Beame

According to our database, Paul Beame authored at least 116 papers between 1986 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Quantum Time-Space Tradeoffs for Matrix Problems.

Paul Beame, Niels Kornerup

Electron. Colloquium Comput. Complex., 2024

Quantum Time-Space Tradeoffs for Matrix Problems.

Paul Beame, Niels Kornerup, Michael Whitmeyer

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Cumulative Memory Lower Bounds for Randomized and Quantum Computation.

Paul Beame, Niels Kornerup

Electron. Colloquium Comput. Complex., 2023

Towards a Complexity Theory of Parallel Computation.

Paul Beame, Pierre McKenzie

Proceedings of the Logic, 2023

2022

On Disperser/Lifting Properties of the Index and Inner-Product Functions.

Paul Beame, Sajin Koroth

Electron. Colloquium Comput. Complex., 2022

Adding Dual Variables to Algebraic Reasoning for Gate-Level Multiplier Verification.

Daniela Kaufmann, Paul Beame, Armin Biere, Jakob Nordström

Proceedings of the 2022 Design, Automation & Test in Europe Conference & Exhibition, 2022

2020

Edge Estimation with Independent Set Oracles.

Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha

ACM Trans. Algorithms, 2020

On the Bias of Reed-Muller Codes over Odd Prime Fields.

Paul Beame, Shayan Oveis Gharan, Xin Yang

SIAM J. Discret. Math., 2020

Technical perspective: Two for the price of one.

Paul Beame

Commun. ACM, 2020

Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning.

Vincent Liew, Paul Beame, Jo Devriendt, Jan Elffers, Jakob Nordström

Proceedings of the 2020 Formal Methods in Computer Aided Design, 2020

2019

Toward Verifying Nonlinear Integer Arithmetic.

Paul Beame, Vincent Liew

J. ACM, 2019

Smoothing Structured Decomposable Circuits.

Andy Shih, Guy Van den Broeck, Paul Beame, Antoine Amarilli

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials.

Paul Beame, Shayan Oveis Gharan, Xin Yang

Electron. Colloquium Comput. Complex., 2018

2017

Exact Model Counting of Query Expressions: Limitations of Propositional Methods.

Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu

ACM Trans. Database Syst., 2017

Communication Steps for Parallel Query Processing.

Paul Beame, Paraschos Koutris, Dan Suciu

J. ACM, 2017

Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions.

Paul Beame, Shayan Oveis Gharan, Xin Yang

Electron. Colloquium Comput. Complex., 2017

Stabbing Planes.

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube.

Paul Beame, Cyrus Rashtchian

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Towards Verifying Nonlinear Integer Arithmetic.

Paul Beame, Vincent Liew

Proceedings of the Computer Aided Verification - 29th International Conference, 2017

2016

Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method.

Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin

ACM Trans. Comput. Theory, 2016

Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.

Paul Beame, Chris Beck, Russell Impagliazzo

SIAM J. Comput., 2016

Communication Cost in Parallel Query Processing.

Paul Beame, Paraschos Koutris, Dan Suciu

CoRR, 2016

Worst-Case Optimal Algorithms for Parallel Query Processing.

Paraschos Koutris, Paul Beame, Dan Suciu

Proceedings of the 19th International Conference on Database Theory, 2016

2015

New Limits for Knowledge Compilation and Applications to Exact Model Counting.

Paul Beame, Vincent Liew

Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 2015

Symmetric Weighted First-Order Model Counting.

Paul Beame, Guy Van den Broeck, Eric Gribkoff, Dan Suciu

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Finding the Median (Obliviously) with Bounded Space.

Paul Beame, Vincent Liew, Mihai Patrascu

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Skew in parallel query processing.

Paul Beame, Paraschos Koutris, Dan Suciu

Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Counting of Query Expressions: Limitations of Propositional Methods.

Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu

Proceedings of the Proc. 17th International Conference on Database Theory (ICDT), 2014

Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution.

Paul Beame, Ashish Sabharwal

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013

Element Distinctness, Frequency Moments, and Sliding Windows.

Paul Beame, Raphaël Clifford, Widad Machmouchi

Electron. Colloquium Comput. Complex., 2013

Model Counting of Query Expressions: Limitations of Propositional Methods.

Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu

CoRR, 2013

Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases.

Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu

Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, 2013

2012

The Value of Multiple Read/Write Streams for Approximating Frequency Moments.

Paul Beame, Trinh Huynh

ACM Trans. Comput. Theory, 2012

Multiparty Communication Complexity and Threshold Circuit Size of sfAC⁰.

Paul Beame, Trinh Huynh

SIAM J. Comput., 2012

The quantum query complexity of AC⁰.

Paul Beame, Widad Machmouchi

Quantum Inf. Comput., 2012

Sliding Windows With Limited Storage.

Paul Beame, Raphaël Clifford, Widad Machmouchi

Electron. Colloquium Comput. Complex., 2012

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT.

Paul Beame, Russell Impagliazzo, Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.

Paul Beame, Chris Beck, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2011

Making Branching Programs Oblivious Requires Superlogarithmic Overhead.

Paul Beame, Widad Machmouchi

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Separating Deterministic from Randomized Multiparty Communication Complexity.

Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel

Theory Comput., 2010

Making RAMs Oblivious Requires Superlogarithmic Overhead.

Paul Beame, Widad Machmouchi

Electron. Colloquium Comput. Complex., 2010

The Quantum Query Complexity of AC0

Paul Beame, Widad Machmouchi

CoRR, 2010

Hardness amplification in proof complexity.

Paul Beame, Trinh Huynh, Toniann Pitassi

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

Hardness Amplification in Proof Complexity.

Paul Beame, Trinh Huynh

Electron. Colloquium Comput. Complex., 2009

Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword.

Paul Beame, Amit Chakrabarti

Comput. Complex., 2009

2008

Multiparty Communication Complexity and Threshold Circuit Size of AC^0.

Paul Beame, Dang-Trinh Huynh-Ngoc

Electron. Colloquium Comput. Complex., 2008

Multiparty Communication Complexity of AC^0.

Paul Beame, Dang-Trinh Huynh-Ngoc

Electron. Colloquium Comput. Complex., 2008

On the Value of Multiple Read/Write Streams for Approximating Frequency Moments.

Paul Beame, Dang-Trinh Huynh-Ngoc

Electron. Colloquium Comput. Complex., 2008

2007

Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.

Paul Beame, Toniann Pitassi, Nathan Segerlind

SIAM J. Comput., 2007

The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.

Paul Beame, Russell Impagliazzo, Ashish Sabharwal

Comput. Complex., 2007

Lower bounds for randomized read/write stream algorithms.

Paul Beame, T. S. Jayram, Atri Rudra

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A Dynamic Approach for MPE and Weighted MAX-SAT.

Tian Sang, Paul Beame, Henry A. Kautz

Proceedings of the IJCAI 2007, 2007

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.

Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

Formula Caching in DPLL.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Electron. Colloquium Comput. Complex., 2006

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Comput. Complex., 2006

2005

Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

Paul Beame, Toniann Pitassi, Nathan Segerlind

Electron. Colloquium Comput. Complex., 2005

The resolution complexity of random graph <i>k</i>-colorability.

Paul Beame, Joseph C. Culberson, David G. Mitchell, Cristopher Moore

Discret. Appl. Math., 2005

Heuristics for Fast Exact Model Counting.

Tian Sang, Paul Beame, Henry A. Kautz

Proceedings of the Theory and Applications of Satisfiability Testing, 2005

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Performing Bayesian Inference by Weighted Model Counting.

Tian Sang, Paul Beame, Henry A. Kautz

Proceedings of the Proceedings, 2005

2004

Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.

Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal

SIAM J. Comput., 2004

A sharp threshold in proof complexity yields lower bounds for satisfiability search.

Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy

J. Comput. Syst. Sci., 2004

Towards Understanding and Harnessing the Potential of Clause Learning.

Paul Beame, Henry A. Kautz, Ashish Sabharwal

J. Artif. Intell. Res., 2004

The Resolution Complexity of Random Graph k-Colorability

Paul Beame, Joseph C. Culberson, David G. Mitchell, Cristopher Moore

Electron. Colloquium Comput. Complex., 2004

Exponential bounds for DPLL below the satisfiability threshold.

Dimitris Achlioptas, Paul Beame, Michael Molloy

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Combining Component Caching and Clause Learning for Effective Model Counting.

Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi

Proceedings of the SAT 2004, 2004

Proof complexity.

Paul Beame

Proceedings of the Computational Complexity Theory., 2004

2003

Time-space trade-off lower bounds for randomized computation of decision problems.

Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee

J. ACM, 2003

Using Problem Structure for Efficient Clause Learning.

Ashish Sabharwal, Paul Beame, Henry A. Kautz

Proceedings of the Theory and Applications of Satisfiability Testing, 2003

Understanding the Power of Clause Learning.

Paul Beame, Henry A. Kautz, Ashish Sabharwal

Proceedings of the IJCAI-03, 2003

Memoization and DPLL: Formula Caching Proof Systems.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

The Efficiency of Resolution and Davis--Putnam Procedures.

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks

SIAM J. Comput., 2002

Optimal Bounds for the Predecessor Problem and Related Problems.

Paul Beame, Faith E. Fich

J. Comput. Syst. Sci., 2002

Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems.

Paul Beame, Erik Vee

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Optimizing Symbolic Model Checking for Statecharts.

William Chan, Richard J. Anderson, Paul Beame, David H. Jones, David Notkin, William E. Warner

IEEE Trans. Software Eng., 2001

Time-Space Tradeoffs for Branching Programs.

Paul Beame, T. S. Jayram, Michael E. Saks

J. Comput. Syst. Sci., 2001

A sharp threshold in proof complexity.

Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Resolution Complexity of Independent Sets in Random Graphs.

Paul Beame, Russell Impagliazzo, Ashish Sabharwal

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Propositional Proof Complexity: Past, Present, and Future.

Paul Beame, Toniann Pitassi

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation

Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee

Electron. Colloquium Comput. Complex., 2000

1999

A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata.

Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa

SIAM J. Comput., 1999

Optimal Bounds for the Predecessor Problem.

Paul Beame, Faith E. Fich

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Decoupling Synchronization from Local Control for Efficient Symbolic Model Checking of Statecharts.

William Chan, Richard J. Anderson, Paul Beame, David H. Jones, David Notkin, William E. Warner

Proceedings of the 1999 International Conference on Software Engineering, 1999

Experiences with the Application of Symbolic Model Checking to the Analysis of Software Specifications.

Richard J. Anderson, Paul Beame, William Chan, David Notkin

Proceedings of the Perspectives of System Informatics, 1999

1998

Model Checking Large Software Specifications.

William Chan, Richard J. Anderson, Paul Beame, Steve Burns, Francesmary Modugno, David Notkin, Jon Damon Reese

IEEE Trans. Software Eng., 1998

The Relative Complexity of NP Search Problems.

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi

J. Comput. Syst. Sci., 1998

Propositional Proof Complexity: Past, Present and Future

Paul Beame, Toniann Pitassi

Electron. Colloquium Comput. Complex., 1998

On Searching Sorted Lists: A Near-Optimal Lower Bound

Paul Beame, Faith E. Fich

Electron. Colloquium Comput. Complex., 1998

Improved Depth Lower Bounds for Small Distance Connectivity.

Paul Beame, Russell Impagliazzo, Toniann Pitassi

Comput. Complex., 1998

On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Improving Efficiency of Symbolic Model Checking for State-Based System Requirements.

William Chan, Richard J. Anderson, Paul Beame, David Notkin

Proceedings of ACM SIGSOFT International Symposium on Software Testing and Analysis, 1998

1997

Separating the Power of EREW and CREW PRAMs with Small Communication Width.

Paul Beame, Faith E. Fich, Rakesh K. Sinha

Inf. Comput., 1997

Combining Constraint Solving and Symbolic Model Checking for a Class of a Systems with Non-linear Constraints.

William Chan, Richard J. Anderson, Paul Beame, David Notkin

Proceedings of the Computer Aided Verification, 9th International Conference, 1997

1996

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata.

Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa

Inf. Comput., 1996

An Exponential Separation Between the Parity Principle and the Pigeonhole Principle.

Paul Beame, Toniann Pitassi

Ann. Pure Appl. Log., 1996

Parallel Algorithms for Arrangements.

Richard J. Anderson, Paul Beame, Erik Brisson

Algorithmica, 1996

Simplified and Improved Resolution Lower Bounds.

Paul Beame, Toniann Pitassi

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

More on the relative strength of counting principles.

Paul Beame, Søren Riis

Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995

Improved Depth Lower Vounds for Small Distance Connectivity.

Paul Beame, Russell Impagliazzo, Toniann Pitassi

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Communication-Space Tradeoffs for Unrestricted Protocols.

Paul Beame, Martin Tompa, Peiyuan Yan

SIAM J. Comput., 1994

Information Broadcasting by Exclusive-Read Prams.

Paul Beame, Miroslaw Kutylowski, Marcin Kik

Parallel Process. Lett., 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Exponential Lower Bounds for the Pigeonhole Principle.

Toniann Pitassi, Paul Beame, Russell Impagliazzo

Comput. Complex., 1993

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

Paul Beame, Toniann Pitassi

Proceedings of the Eighth Annual Symposium on Logic in Computer Science (LICS '93), 1993

1992

The Complexity of Computing Symmetric Functions Using Threshold Circuits.

Paul Beame, Erik Brisson, Richard E. Ladner

Theor. Comput. Sci., 1992

Randomized versus Nondeterministic Communication Complexity

Paul Beame, Joan Lawry

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Exponential Lower Bounds for the Pigeonhole Principle

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

A General Sequential Time-Space Tradeoff for Finding Unique Elements.

Paul Beame

SIAM J. Comput., 1991

1990

Lower bounds for recognizing small cliques on CRCW PRAM's.

Paul Beame

Discret. Appl. Math., 1990

Low Overhead Parallel Schedules for Task Graphs.

Richard J. Anderson, Paul Beame, Walter L. Ruzzo

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

Parallel Search for Maximal Independence Given Minimal Dependence.

Paul Beame, Michael Luby

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Time-Space Tradeoffs for Undirected Graph Traversal

Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Optimal bounds for decision problems on the CRCW PRAM.

Paul Beame, Johan Håstad

J. ACM, 1989

Distributed Computing on TRansitive Networks: The Thorus.

Paul Beame, Hans L. Bodlaender

Proceedings of the STACS 89, 1989

1988

Limits on the Power of Concurrent-Write Parallel Machines

Paul Beame

Inf. Comput., January, 1988

1986

Log Depth Circuits for Division and Related Problems.

Paul Beame, Stephen A. Cook, H. James Hoover

SIAM J. Comput., 1986