| 2026 | SAT | Extending CDCL to Disjunctions of Parity Equations. | Paul Beame, Glenn Sun |
| 2025 | ICALP | Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. | Paul Beame, Michael Whitmeyer |
| 2024 | STOC | Quantum Time-Space Tradeoffs for Matrix Problems. | Paul Beame, Niels Kornerup, Michael Whitmeyer |
| 2023 | ICALP | Cumulative Memory Lower Bounds for Randomized and Quantum Computation. | Paul Beame, Niels Kornerup |
| 2022 | DATE | Adding Dual Variables to Algebraic Reasoning for Gate-Level Multiplier Verification. | Daniela Kaufmann, Paul Beame, Armin Biere, Jakob Nordstrm |
| 2020 | FMCAD | Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning. | Vincent Liew, Paul Beame, Jo Devriendt, Jan Elffers, Jakob Nordstrm |
| 2018 | COLT | Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. | Paul Beame, Shayan Oveis Gharan, Xin Yang |
| 2017 | CAV | Towards Verifying Nonlinear Integer Arithmetic. | Paul Beame, Vincent Liew |
| 2017 | SODA | Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube. | Paul Beame, Cyrus Rashtchian |
| 2016 | ICDT | Worst-Case Optimal Algorithms for Parallel Query Processing. | Paraschos Koutris, Paul Beame, Dan Suciu |
| 2015 | ICALP | Finding the Median (Obliviously) with Bounded Space. | Paul Beame, Vincent Liew, Mihai Patrascu |
| 2015 | PODS | Symmetric Weighted First-Order Model Counting. | Paul Beame, Guy Van den Broeck, Eric Gribkoff, Dan Suciu |
| 2015 | UAI | New Limits for Knowledge Compilation and Applications to Exact Model Counting. | Paul Beame, Vincent Liew |
| 2014 | AAAI | Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution. | Paul Beame, Ashish Sabharwal |
| 2014 | ICDT | Counting of Query Expressions: Limitations of Propositional Methods. | Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu |
| 2014 | PODS | Skew in parallel query processing. | Paul Beame, Paraschos Koutris, Dan Suciu |
| 2013 | FOCS | Element Distinctness, Frequency Moments, and Sliding Windows. | Paul Beame, Raphal Clifford, Widad Machmouchi |
| 2013 | PODS | Communication steps for parallel query processing. | Paul Beame, Paraschos Koutris, Dan Suciu |
| 2013 | UAI | Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases. | Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu |
| 2012 | STOC | Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. | Paul Beame, Christopher Beck, Russell Impagliazzo |
| 2010 | STOC | Hardness amplification in proof complexity. | Paul Beame, Trinh Huynh, Toniann Pitassi |
| 2009 | FOCS | Multiparty Communication Complexity and Threshold Circuit Size of AC^0. | Paul Beame, Dang-Trinh Huynh-Ngoc |
| 2008 | FOCS | On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. | Paul Beame, Dang-Trinh Huynh-Ngoc |
| 2007 | ICALP | Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. | Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel |
| 2007 | IJCAI | A Dynamic Approach for MPE and Weighted MAX-SAT. | Tian Sang, Paul Beame, Henry A. Kautz |
| 2007 | STOC | Lower bounds for randomized read/write stream algorithms. | Paul Beame, T. S. Jayram, Atri Rudra |
| 2005 | AAAI | Performing Bayesian Inference by Weighted Model Counting. | Tian Sang, Paul Beame, Henry A. Kautz |
| 2005 | ICALP | Lower Bounds for Lovsz-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. | Paul Beame, Toniann Pitassi, Nathan Segerlind |
| 2005 | SAT | Heuristics for Fast Exact Model Counting. | Tian Sang, Paul Beame, Henry A. Kautz |
| 2004 | SODA | Exponential bounds for DPLL below the satisfiability threshold. | Dimitris Achlioptas, Paul Beame, Michael Molloy |
| 2004 | SAT | Combining Component Caching and Clause Learning for Effective Model Counting. | Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi |
| 2003 | IJCAI | Understanding the Power of Clause Learning. | Paul Beame, Henry A. Kautz, Ashish Sabharwal |
| 2003 | SAT | Using Problem Structure for Efficient Clause Learning. | Ashish Sabharwal, Paul Beame, Henry A. Kautz |
| 2002 | FOCS | Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. | Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal |
| 2002 | STOC | Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. | Paul Beame, Erik Vee |
| 2001 | STOC | A sharp threshold in proof complexity. | Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy |
| 2000 | FOCS | Super-linear time-space tradeoff lower bounds for randomized computation. | Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee |
| 1999 | ICSE | 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 |
| 1999 | STOC | Optimal Bounds for the Predecessor Problem. | Paul Beame, Faith E. Fich |
| 1998 | FOCS | Time-Space Tradeoffs for Branching Programs. | Paul Beame, Michael E. Saks, Jayram S. Thathachar |
| 1998 | ISSTA | Improving Efficiency of Symbolic Model Checking for State-Based System Requirements. | William Chan, Richard J. Anderson, Paul Beame, David Notkin |
| 1998 | STOC | On the Complexity of Unsatisfiability Proofs for Random | Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks |
| 1997 | CAV | 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 |
| 1996 | FOCS | Simplified and Improved Resolution Lower Bounds. | Paul Beame, Toniann Pitassi |
| 1995 | FOCS | Improved Depth Lower Vounds for Small Distance Connectivity. | Paul Beame, Russell Impagliazzo, Toniann Pitassi |
| 1995 | STOC | The relative complexity of NP search problems. | Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi |
| 1994 | FOCS | Lower Bound on Hilbert's Nullstellensatz and propositional proofs | Paul Beame, Russell Impagliazzo, Jan Krajcek, Toniann Pitassi, Pavel Pudlk |
| 1993 | LICS | An Exponential Separation between the Matching Principle and the Pigeonhole Principle | Paul Beame, Toniann Pitassi |
| 1993 | WADS | Separating the Power of EREW and CREW PRAMs with Small Communication Width. | Paul Beame, Faith E. Fich, Rakesh K. Sinha |
| 1992 | STOC | Exponential Lower Bounds for the Pigeonhole Principle | Paul Beame, Russell Impagliazzo, Jan Krajcek, Toniann Pitassi, Pavel Pudlk, Alan R. Woods |
| 1992 | STOC | Randomized versus Nondeterministic Communication Complexity | Paul Beame, Joan Lawry |
| 1990 | FOCS | Time-Space Tradeoffs for Undirected Graph Traversal | Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa |
| 1990 | FOCS | Communication-Space Tradeoffs for Unrestricted Protocols | Paul Beame, Martin Tompa, Peiyuan Yan |
| 1990 | SODA | Parallel Search for Maximal Independence Given Minimal Dependence. | Paul Beame, Michael Luby |
| 1990 | SPAA | Parallel Algorithms for Arrangements. | Richard J. Anderson, Paul Beame, Erik Brisson |
| 1990 | SPAA | Low Overhead Parallel Schedules for Task Graphs. | Richard J. Anderson, Paul Beame, Walter L. Ruzzo |
| 1989 | STOC | A General Sequential Time-Space Tradeoff for Finding Unique Elements | Paul Beame |
| 1989 | STACS | Distributed Computing on TRansitive Networks: The Thorus. | Paul Beame, Hans L. Bodlaender |
| 1987 | STOC | Optimal Bounds for Decision Problems on the CRCW PRAM | Paul Beame, Johan Hstad |
| 1986 | STOC | Limits on the Power of Concurrent-Write Parallel Machines | Paul Beame |
| 1984 | FOCS | Log Depth Circuits for Division and Related Problems | Paul Beame, Stephen A. Cook, H. James Hoover |