Paul Beame - RankMe

171 papers A* 45A 19B 4Journal 94Unranked 5

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Cumulative Memory Lower Bounds for Randomized and Quantum Computation. ACM Trans. Comput. Theory Paul Beame, Niels Kornerup
2025	A*	`conf`	Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. ICALP Paul Beame, Michael Whitmeyer
2025	J	`jnl`	Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. Electron. Colloquium Comput. Complex. Paul Beame, Michael Whitmeyer
2024	J	`jnl`	Multiparty Communication Complexity of Collision Finding. CoRR Paul Beame, Michael Whitmeyer
2024	A*	`conf`	Quantum Time-Space Tradeoffs for Matrix Problems. STOC Paul Beame, Niels Kornerup, Michael Whitmeyer
2024	J	`jnl`	Quantum Time-Space Tradeoffs for Matrix Problems. CoRR Paul Beame, Niels Kornerup
2024	J	`jnl`	Quantum Time-Space Tradeoffs for Matrix Problems. Electron. Colloquium Comput. Complex. Paul Beame, Niels Kornerup
2023	A*	`conf`	Cumulative Memory Lower Bounds for Randomized and Quantum Computation. ICALP Paul Beame, Niels Kornerup
2023	J	`jnl`	Cumulative Memory Lower Bounds for Randomized and Quantum Computation. CoRR Paul Beame, Niels Kornerup
2023	J	`jnl`	Cumulative Memory Lower Bounds for Randomized and Quantum Computation. Electron. Colloquium Comput. Complex. Paul Beame, Niels Kornerup
2023	A	`conf`	On Disperser/Lifting Properties of the Index and Inner-Product Functions. ITCS Paul Beame, Sajin Koroth
2023	—	`ch.`	Towards a Complexity Theory of Parallel Computation. Logic, Automata, and Computational Complexity Paul Beame, Pierre McKenzie
2022	A	`conf`	Adding Dual Variables to Algebraic Reasoning for Gate-Level Multiplier Verification. DATE Daniela Kaufmann, Paul Beame, Armin Biere, Jakob Nordström
2022	J	`jnl`	On Disperser/Lifting Properties of the Index and Inner-Product Functions. CoRR Paul Beame, Sajin Koroth
2022	J	`jnl`	On Disperser/Lifting Properties of the Index and Inner-Product Functions. Electron. Colloquium Comput. Complex. Paul Beame, Sajin Koroth
2020	J	`jnl`	Edge Estimation with Independent Set Oracles. ACM Trans. Algorithms Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha
2020	J	`jnl`	On the Bias of Reed-Muller Codes over Odd Prime Fields. SIAM J. Discret. Math. Paul Beame, Shayan Oveis Gharan, Xin Yang
2020	J	`jnl`	Technical perspective: Two for the price of one. Commun. ACM Paul Beame
2020	B	`conf`	Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning. FMCAD Vincent Liew, Paul Beame, Jo Devriendt, Jan Elffers, Jakob Nordström
2019	A*	`conf`	Smoothing Structured Decomposable Circuits. NeurIPS Andy Shih, Guy Van den Broeck, Paul Beame, Antoine Amarilli
2019	J	`jnl`	Smoothing Structured Decomposable Circuits. CoRR Andy Shih, Guy Van den Broeck, Paul Beame, Antoine Amarilli
2019	J	`jnl`	Toward Verifying Nonlinear Integer Arithmetic. J. ACM Paul Beame, Vincent Liew
2018	A	`conf`	Edge Estimation with Independent Set Oracles. ITCS Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha
2018	J	`jnl`	On the Bias of Reed-Muller Codes over Odd Prime Fields. CoRR Paul Beame, Shayan Oveis Gharan, Xin Yang
2018	A	`conf`	Stabbing Planes. ITCS Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2018	A*	`conf`	Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. COLT Paul Beame, Shayan Oveis Gharan, Xin Yang
2018	J	`jnl`	Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. Electron. Colloquium Comput. Complex. Paul Beame, Shayan Oveis Gharan, Xin Yang
2017	J	`jnl`	Communication Steps for Parallel Query Processing. J. ACM Paul Beame, Paraschos Koutris, Dan Suciu
2017	J	`jnl`	Edge Estimation with Independent Set Oracles. CoRR Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha
2017	J	`jnl`	Exact Model Counting of Query Expressions: Limitations of Propositional Methods. ACM Trans. Database Syst. Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
2017	A*	`conf`	Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube. SODA Paul Beame, Cyrus Rashtchian
2017	J	`jnl`	Stabbing Planes. CoRR Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2017	J	`jnl`	Stabbing Planes. Electron. Colloquium Comput. Complex. Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2017	J	`jnl`	Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. CoRR Paul Beame, Shayan Oveis Gharan, Xin Yang
2017	J	`jnl`	Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. Electron. Colloquium Comput. Complex. Paul Beame, Shayan Oveis Gharan, Xin Yang
2017	—	`conf`	Towards Verifying Nonlinear Integer Arithmetic. CAV (2) Paul Beame, Vincent Liew
2017	J	`jnl`	Towards Verifying Nonlinear Integer Arithmetic. CoRR Paul Beame, Vincent Liew
2016	J	`jnl`	Communication Cost in Parallel Query Processing. CoRR Paul Beame, Paraschos Koutris, Dan Suciu
2016	J	`jnl`	Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube. CoRR Paul Beame, Cyrus Rashtchian
2016	J	`jnl`	Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method. ACM Trans. Comput. Theory Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin
2016	J	`jnl`	Nondeterminism and an abstract formulation of Nečiporuk's lower bound method. CoRR Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin
2016	J	`jnl`	Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. SIAM J. Comput. Paul Beame, Chris Beck, Russell Impagliazzo
2016	A	`conf`	Worst-Case Optimal Algorithms for Parallel Query Processing. ICDT Paraschos Koutris, Paul Beame, Dan Suciu
2016	J	`jnl`	Worst-Case Optimal Algorithms for Parallel Query Processing. CoRR Paul Beame, Paraschos Koutris, Dan Suciu
2015	—	`conf`	Finding the Median (Obliviously) with Bounded Space. ICALP (1) Paul Beame, Vincent Liew, Mihai Patrascu
2015	J	`jnl`	Finding the Median (Obliviously) with Bounded Space. CoRR Paul Beame, Vincent Liew, Mihai Patrascu
2015	A	`conf`	New Limits for Knowledge Compilation and Applications to Exact Model Counting. UAI Paul Beame, Vincent Liew
2015	J	`jnl`	New Limits for Knowledge Compilation and Applications to Exact Model Counting. CoRR Paul Beame, Vincent Liew
2015	A*	`conf`	Symmetric Weighted First-Order Model Counting. PODS Paul Beame, Guy Van den Broeck, Eric Gribkoff, Dan Suciu
2014	A	`conf`	Counting of Query Expressions: Limitations of Propositional Methods. ICDT Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
2014	A*	`conf`	Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution. AAAI Paul Beame, Ashish Sabharwal
2014	J	`jnl`	Skew in Parallel Query Processing. CoRR Paul Beame, Paraschos Koutris, Dan Suciu
2014	A*	`conf`	Skew in parallel query processing. PODS Paul Beame, Paraschos Koutris, Dan Suciu
2014	J	`jnl`	Symmetric Weighted First-Order Model Counting. CoRR Paul Beame, Guy Van den Broeck, Eric Gribkoff, Dan Suciu
2013	J	`jnl`	Communication Steps for Parallel Query Processing. CoRR Paul Beame, Paraschos Koutris, Dan Suciu
2013	A*	`conf`	Communication steps for parallel query processing. PODS Paul Beame, Paraschos Koutris, Dan Suciu
2013	A*	`conf`	Element Distinctness, Frequency Moments, and Sliding Windows. FOCS Paul Beame, Raphaël Clifford, Widad Machmouchi
2013	J	`jnl`	Element Distinctness, Frequency Moments, and Sliding Windows. CoRR Paul Beame, Raphaël Clifford, Widad Machmouchi
2013	J	`jnl`	Element Distinctness, Frequency Moments, and Sliding Windows. Electron. Colloquium Comput. Complex. Paul Beame, Raphaël Clifford, Widad Machmouchi
2013	A	`conf`	Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases. UAI Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
2013	J	`jnl`	Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases. CoRR Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
2013	J	`jnl`	Model Counting of Query Expressions: Limitations of Propositional Methods. CoRR Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
2012	A	`conf`	Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. CCC Paul Beame, Russell Impagliazzo, Srikanth Srinivasan
2012	J	`jnl`	Multiparty Communication Complexity and Threshold Circuit Size of sfAC SIAM J. Comput. Paul Beame, Trinh Huynh
2012	J	`jnl`	Sliding Windows With Limited Storage. Electron. Colloquium Comput. Complex. Paul Beame, Raphaël Clifford, Widad Machmouchi
2012	J	`jnl`	Sliding Windows with Limited Storage CoRR Paul Beame, Raphaël Clifford, Widad Machmouchi
2012	J	`jnl`	The Value of Multiple Read/Write Streams for Approximating Frequency Moments. ACM Trans. Comput. Theory Paul Beame, Trinh Huynh
2012	J	`jnl`	The quantum query complexity of AC Quantum Inf. Comput. Paul Beame, Widad Machmouchi
2012	A*	`conf`	Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC Paul Beame, Christopher Beck, Russell Impagliazzo
2011	A	`conf`	Making Branching Programs Oblivious Requires Superlogarithmic Overhead. CCC Paul Beame, Widad Machmouchi
2011	J	`jnl`	Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. Electron. Colloquium Comput. Complex. Paul Beame, Chris Beck, Russell Impagliazzo
2011	J	`jnl`	Towards Understanding and Harnessing the Potential of Clause Learning CoRR Paul Beame, Henry A. Kautz, Ashish Sabharwal
2010	J	`jnl`	Formula Caching in DPLL. ACM Trans. Comput. Theory Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2010	A*	`conf`	Hardness amplification in proof complexity. STOC Paul Beame, Trinh Huynh, Toniann Pitassi
2010	J	`jnl`	Making RAMs Oblivious Requires Superlogarithmic Overhead. Electron. Colloquium Comput. Complex. Paul Beame, Widad Machmouchi
2010	J	`jnl`	Separating Deterministic from Randomized Multiparty Communication Complexity. Theory Comput. Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel
2010	J	`jnl`	The Quantum Query Complexity of AC0 CoRR Paul Beame, Widad Machmouchi
2009	J	`jnl`	Hardness Amplification in Proof Complexity CoRR Paul Beame, Trinh Huynh, Toniann Pitassi
2009	J	`jnl`	Hardness Amplification in Proof Complexity. Electron. Colloquium Comput. Complex. Paul Beame, Trinh Huynh
2009	A*	`conf`	Multiparty Communication Complexity and Threshold Circuit Size of AC^0. FOCS Paul Beame, Dang-Trinh Huynh-Ngoc
2009	J	`jnl`	Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. Comput. Complex. Paul Beame, Amit Chakrabarti
2008	J	`jnl`	Multiparty Communication Complexity and Threshold Circuit Size of AC^0. Electron. Colloquium Comput. Complex. Paul Beame, Dang-Trinh Huynh-Ngoc
2008	J	`jnl`	Multiparty Communication Complexity of AC^0. Electron. Colloquium Comput. Complex. Paul Beame, Dang-Trinh Huynh-Ngoc
2008	A*	`conf`	On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. FOCS Paul Beame, Dang-Trinh Huynh-Ngoc
2008	J	`jnl`	On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. Electron. Colloquium Comput. Complex. Paul Beame, Dang-Trinh Huynh-Ngoc
2007	A*	`conf`	A Dynamic Approach for MPE and Weighted MAX-SAT. IJCAI Tian Sang, Paul Beame, Henry A. Kautz
2007	J	`jnl`	Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. SIAM J. Comput. Paul Beame, Toniann Pitassi, Nathan Segerlind
2007	A*	`conf`	Lower bounds for randomized read/write stream algorithms. STOC Paul Beame, T. S. Jayram, Atri Rudra
2007	A*	`conf`	Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. ICALP Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel
2007	J	`jnl`	The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Comput. Complex. Paul Beame, Russell Impagliazzo, Ashish Sabharwal
2006	J	`jnl`	A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. Comput. Complex. Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
2006	J	`jnl`	Formula Caching in DPLL. Electron. Colloquium Comput. Complex. Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2005	A	`conf`	A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. CCC Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
2005	A	`conf`	Heuristics for Fast Exact Model Counting. SAT Tian Sang, Paul Beame, Henry A. Kautz
2005	A*	`conf`	Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. ICALP Paul Beame, Toniann Pitassi, Nathan Segerlind
2005	J	`jnl`	Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity Electron. Colloquium Comput. Complex. Paul Beame, Toniann Pitassi, Nathan Segerlind
2005	A*	`conf`	Performing Bayesian Inference by Weighted Model Counting. AAAI Tian Sang, Paul Beame, Henry A. Kautz
2005	J	`jnl`	The resolution complexity of random graph Discret. Appl. Math. Paul Beame, Joseph C. Culberson, David G. Mitchell, Cristopher Moore
2004	J	`jnl`	A sharp threshold in proof complexity yields lower bounds for satisfiability search. J. Comput. Syst. Sci. Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy
2004	J	`jnl`	Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. SIAM J. Comput. Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal
2004	A	`conf`	Combining Component Caching and Clause Learning for Effective Model Counting. SAT Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi
2004	A*	`conf`	Exponential bounds for DPLL below the satisfiability threshold. SODA Dimitris Achlioptas, Paul Beame, Michael Molloy
2004	—	`ch.`	Proof complexity. Computational Complexity Theory Paul Beame
2004	J	`jnl`	The Resolution Complexity of Random Graph k-Colorability Electron. Colloquium Comput. Complex. Paul Beame, Joseph C. Culberson, David G. Mitchell, Cristopher Moore
2004	J	`jnl`	Towards Understanding and Harnessing the Potential of Clause Learning. J. Artif. Intell. Res. Paul Beame, Henry A. Kautz, Ashish Sabharwal
2003	A	`conf`	Memoization and DPLL: Formula Caching Proof Systems. CCC Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2003	J	`jnl`	Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee
2003	A*	`conf`	Understanding the Power of Clause Learning. IJCAI Paul Beame, Henry A. Kautz, Ashish Sabharwal
2003	A	`conf`	Using Problem Structure for Efficient Clause Learning. SAT Ashish Sabharwal, Paul Beame, Henry A. Kautz
2002	A*	`conf`	Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. FOCS Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal
2002	J	`jnl`	Bounded-depth Frege lower bounds for weaker pigeonhole principles Electron. Colloquium Comput. Complex. Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal
2002	J	`jnl`	Optimal Bounds for the Predecessor Problem and Related Problems. J. Comput. Syst. Sci. Paul Beame, Faith E. Fich
2002	J	`jnl`	The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks
2002	A	`conf`	Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. CCC Paul Beame, Erik Vee
2002	A*	`conf`	Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. STOC Paul Beame, Erik Vee
2001	A*	`conf`	A sharp threshold in proof complexity. STOC Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy
2001	J	`jnl`	Optimizing Symbolic Model Checking for Statecharts. IEEE Trans. Software Eng. William Chan, Richard J. Anderson, Paul Beame, David H. Jones, David Notkin, William E. Warner
2001	—	`ch.`	Propositional Proof Complexity: Past, Present, and Future. Current Trends in Theoretical Computer Science Paul Beame, Toniann Pitassi
2001	A	`conf`	Resolution Complexity of Independent Sets in Random Graphs. CCC Paul Beame, Russell Impagliazzo, Ashish Sabharwal
2001	J	`jnl`	Time-Space Tradeoffs for Branching Programs. J. Comput. Syst. Sci. Paul Beame, T. S. Jayram, Michael E. Saks
2000	J	`jnl`	Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation Electron. Colloquium Comput. Complex. Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee
2000	A*	`conf`	Super-linear time-space tradeoff lower bounds for randomized computation. FOCS Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee
1999	J	`jnl`	A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. SIAM J. Comput. Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
1999	A*	`conf`	Decoupling Synchronization from Local Control for Efficient Symbolic Model Checking of Statecharts. ICSE William Chan, Richard J. Anderson, Paul Beame, David H. Jones, David Notkin, William E. Warner
1999	—	`conf`	Experiences with the Application of Symbolic Model Checking to the Analysis of Software Specifications. Ershov Memorial Conference Richard J. Anderson, Paul Beame, William Chan, David Notkin
1999	A*	`conf`	Optimal Bounds for the Predecessor Problem. STOC Paul Beame, Faith E. Fich
1998	J	`jnl`	Improved Depth Lower Bounds for Small Distance Connectivity. Comput. Complex. Paul Beame, Russell Impagliazzo, Toniann Pitassi
1998	A	`conf`	Improving Efficiency of Symbolic Model Checking for State-Based System Requirements. ISSTA William Chan, Richard J. Anderson, Paul Beame, David Notkin
1998	J	`jnl`	Model Checking Large Software Specifications. IEEE Trans. Software Eng. William Chan, Richard J. Anderson, Paul Beame, Steve Burns, Francesmary Modugno, David Notkin, Jon Damon Reese
1998	J	`jnl`	On Searching Sorted Lists: A Near-Optimal Lower Bound Electron. Colloquium Comput. Complex. Paul Beame, Faith E. Fich
1998	A*	`conf`	On the Complexity of Unsatisfiability Proofs for Random STOC Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks
1998	—	`ed.`	Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996 Proof Complexity and Feasible Arithmetics Paul Beame, Samuel R. Buss
1998	J	`jnl`	Propositional Proof Complexity: Past, Present and Future Electron. Colloquium Comput. Complex. Paul Beame, Toniann Pitassi
1998	J	`jnl`	Propositional Proof Complexity: Past, Present and Future. Bull. EATCS Paul Beame, Toniann Pitassi
1998	J	`jnl`	The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
1998	J	`jnl`	Time-Space Tradeoffs for Branching Programs Electron. Colloquium Comput. Complex. Paul Beame, Michael E. Saks, Jayram S. Thathachar
1998	A*	`conf`	Time-Space Tradeoffs for Branching Programs. FOCS Paul Beame, Michael E. Saks, Jayram S. Thathachar
1997	A*	`conf`	Combining Constraint Solving and Symbolic Model Checking for a Class of a Systems with Non-linear Constraints. CAV William Chan, Richard J. Anderson, Paul Beame, David Notkin
1997	J	`jnl`	Separating the Power of EREW and CREW PRAMs with Small Communication Width. Inf. Comput. Paul Beame, Faith E. Fich, Rakesh K. Sinha
1996	J	`jnl`	An Exponential Separation Between the Parity Principle and the Pigeonhole Principle. Ann. Pure Appl. Log. Paul Beame, Toniann Pitassi
1996	—	`conf`	Model Checking Large Software Specifications. SIGSOFT FSE Richard J. Anderson, Paul Beame, Steve Burns, William Chan, Francesmary Modugno, David Notkin, Jon Damon Reese
1996	—	`conf`	More on the relative strength of counting principles. Proof Complexity and Feasible Arithmetics Paul Beame, Søren Riis
1996	J	`jnl`	Parallel Algorithms for Arrangements. Algorithmica Richard J. Anderson, Paul Beame, Erik Brisson
1996	A*	`conf`	Simplified and Improved Resolution Lower Bounds. FOCS Paul Beame, Toniann Pitassi
1996	J	`jnl`	Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata. Inf. Comput. Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
1995	A*	`conf`	Improved Depth Lower Vounds for Small Distance Connectivity. FOCS Paul Beame, Russell Impagliazzo, Toniann Pitassi
1995	A*	`conf`	The relative complexity of NP search problems. STOC Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
1994	J	`jnl`	Communication-Space Tradeoffs for Unrestricted Protocols. SIAM J. Comput. Paul Beame, Martin Tompa, Peiyuan Yan
1994	J	`jnl`	Information Broadcasting by Exclusive-Read Prams. Parallel Process. Lett. Paul Beame, Miroslaw Kutylowski, Marcin Kik
1994	A*	`conf`	Lower Bound on Hilbert's Nullstellensatz and propositional proofs FOCS Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák
1993	A*	`conf`	An Exponential Separation between the Matching Principle and the Pigeonhole Principle LICS Paul Beame, Toniann Pitassi
1993	J	`jnl`	Exponential Lower Bounds for the Pigeonhole Principle. Comput. Complex. Toniann Pitassi, Paul Beame, Russell Impagliazzo
1993	B	`conf`	Separating the Power of EREW and CREW PRAMs with Small Communication Width. WADS Paul Beame, Faith E. Fich, Rakesh K. Sinha
1992	A*	`conf`	Exponential Lower Bounds for the Pigeonhole Principle STOC Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods
1992	A*	`conf`	Randomized versus Nondeterministic Communication Complexity STOC Paul Beame, Joan Lawry
1992	J	`jnl`	The Complexity of Computing Symmetric Functions Using Threshold Circuits. Theor. Comput. Sci. Paul Beame, Erik Brisson, Richard E. Ladner
1991	J	`jnl`	A General Sequential Time-Space Tradeoff for Finding Unique Elements. SIAM J. Comput. Paul Beame
1990	A*	`conf`	Communication-Space Tradeoffs for Unrestricted Protocols FOCS Paul Beame, Martin Tompa, Peiyuan Yan
1990	B	`conf`	Low Overhead Parallel Schedules for Task Graphs. SPAA Richard J. Anderson, Paul Beame, Walter L. Ruzzo
1990	J	`jnl`	Lower bounds for recognizing small cliques on CRCW PRAM's. Discret. Appl. Math. Paul Beame
1990	B	`conf`	Parallel Algorithms for Arrangements. SPAA Richard J. Anderson, Paul Beame, Erik Brisson
1990	A*	`conf`	Parallel Search for Maximal Independence Given Minimal Dependence. SODA Paul Beame, Michael Luby
1990	A*	`conf`	Time-Space Tradeoffs for Undirected Graph Traversal FOCS Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
1989	A*	`conf`	A General Sequential Time-Space Tradeoff for Finding Unique Elements STOC Paul Beame
1989	A	`conf`	Distributed Computing on TRansitive Networks: The Thorus. STACS Paul Beame, Hans L. Bodlaender
1989	J	`jnl`	Optimal bounds for decision problems on the CRCW PRAM. J. ACM Paul Beame, Johan Håstad
1988	J	`jnl`	Limits on the Power of Concurrent-Write Parallel Machines Inf. Comput. Paul Beame
1987	A*	`conf`	Optimal Bounds for Decision Problems on the CRCW PRAM STOC Paul Beame, Johan Håstad
1986	A*	`conf`	Limits on the Power of Concurrent-Write Parallel Machines STOC Paul Beame
1986	J	`jnl`	Log Depth Circuits for Division and Related Problems. SIAM J. Comput. Paul Beame, Stephen A. Cook, H. James Hoover
1984	A*	`conf`	Log Depth Circuits for Division and Related Problems FOCS Paul Beame, Stephen A. Cook, H. James Hoover