Contact

CSE 668
206-543-5114
beamecs.washington.edu
Areas of interest: 

Computational complexity, proof complexity and satisfiability

Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning

V. Liew, P. Beame, J. Devriendt, J. Elfers, J. NordströmProceedings of the 20th Conference on Formal Methods in Computer Aided Design – FMCAD 2020TU Wein Academic Press, 2020.

Edge Estimation with Independent Set Oracles

P. Beame, S. Har-Peled, S.Natarajan Ramamoorthy, C. Rashtchian, M. SinhaACM Transactions on Algorithms 16:4, 2020.

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

P. Beame, S.Oveis Gharan, X. YangSIAM Journal on Discrete Mathematics 34:2, 2020.

Toward Verifying Nonlinear Integer Arithmetic

P. Beame, V. LiewJournal of the ACM 66:3, 2019.

Smoothing Structured Decomposable Circuits

A. Shih, G. Van den Broeck, P. Beame, A. AmarilliAdvances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 2019.

Smoothing Structured Decomposable Circuits

A. Shih, G. Van den Broeck, P. Beame, A. AmarilliCoRR abs/1906.00311, 2019.

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

P. Beame, S.Oveis Gharan, X. YangProceedings of the 31st Conference on Learning Theory, COLT 2018, 2018.

Edge Estimation with Independent Set Oracles

P. Beame, S. Har-Peled, S.Natarajan Ramamoorthy, C. Rashtchian, M. SinhaProceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 94, 2018.

Stabbing Planes

P. Beame, N. Fleming, R. Impagliazzo, A. Kolokolova, D. Pankratov, T. Pitassi, R. RobereProceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 94, 2018.

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

P. Beame, S.Oveis Gharan, X. YangElectronic Colloquium in Computational Complexity:TR18-114, 2018.

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

P. Beame, S.Oveis Gharan, X. YangCoRR abs/1806.06973, 2018.

Communication Steps for Parallel Query Processing

P. Beame, P. Koutris, D. SuciuJournal of the ACM 64:6, 2017.  Preliminary material in Proceedings of 2013 and 2014 ACM Symposium on Principles of Database Systems.

Towards Verifying Nonlinear Integer Arithmetic

P. Beame, V. LiewComputer Aided Verification, 29th International Conference, CAV'17 Proceedings, Part II, 2017.

Towards Verifying Nonlinear Integer Arithmetic

P. Beame, V. LiewCoRR abs/1705.04302, 2017.

Exact Model Counting of Query Expressions: Limitations of Propositional Methods

P. Beame, J. Li, S. Roy, D. SuciuACM Transactions on Database Systems 42:1, 2017.  Invited paper from 2014 International Conference on Database Theory (ICDT) combined with preliminary version in Proceedings of the 2013 Conference on Uncertainty in Artificial Intelligence (UAI).

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

P. Beame, C. RashtchianProceedings of the Twenty-Eighth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2017.

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

P. Beame, S.Oveis Gharan, X. YangCoRR abs/1708.02640, 2017.  Also July 2017 Technical Report TR17-120 # eccc # available at http://eccc.uni-trier.de/eccc-reports/2017/120/index.html

Stabbing Planes

P. Beame, N. Fleming, R. Impagliazzo, A. Kolokolova, D. Pankratov, T. Pitassi, R. RobereCoRR abs/1710.03219, 2017.  Also Technical Report TR17-151 # eccc # available at http://eccc.uni-trier.de/eccc-reports/2017/151/index.html

Nondeterminism and an abstract formulation of Nečiporuk's lower bound method

P. Beame, N. Grosshans, P. McKenzie, L. SegoufinCoRR abs/1608.01932, 2016.

Worst-Case Optimal Algorithms for Parallel Query Processing

P. Koutris, P. Beame, D. SuciuProceedings of 19th International Conference on Database Theory, 2016.

Worst-Case Optimal Algorithms for Parallel Query Processing

P. Beame, P. Koutris, D. SuciuCoRR abs/1604.01848, 2016.

Communication Cost in Parallel Query Processing

P. Beame, P. Koutris, D. SuciuCoRR abs/1602.06236, 2016.

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

P. Beame, N. Grosshans, P. McKenzie, L. SegoufinACM Transactions on Computation Theory 9:1, 2016.

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

P. Beame, C. Beck, R. ImpagliazzoSIAM Journal on Computing 45:4, 2016.

New Limits for Knowledge Compilation and Applications to Exact Model Counting

P. Beame, V. LiewProceedings 31st Conference on Uncertainty in Artificial Intelligence, 2015.

Symmetric Weighted First-Order Model Counting

P. Beame, G. Van den Broeck, E. Gribkoff, D. SuciuProceedings of the Thirty-Fourth Annual ACM Symposium on Principles of Database Systems, 2015.

Finding the Median (Obliviously) with Bounded Space

P. Beame, V. Liew, M. PatrascuAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 2015.

New Limits for Knowledge Compilation and Applications to Exact Model Counting

P. Beame, V. LiewCoRR abs/1506.02639, 2015.

Finding the Median (Obliviously) with Bounded Space

P. Beame, V. Liew, M. PatrascuCoRR abs/1505.00090, 2015.

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

P. Beame, A. SabharwalProceedings, AAAI-14: Twenty-Eighth National Conference on Artificial IntelligenceAmerican Association for Artificial Intelligence, 2014.

Skew in Parallel Query Processing

P. Beame, P. Koutris, D. SuciuProceedings of the Thirty-Third Annual ACM Symposium on Principles of Database Systems, 2014.

Model Counting of Query Expressions: Limitations of Propositional Methods

P. Beame, J. Li, S. Roy, D. SuciuProceedings of 17th International Conference on Database Theory, 2014.

Skew in Parallel Query Processing

P. Beame, P. Koutris, D. SuciuCoRR abs/1401.1872, 2014.

Symmetric Weighted First-Order Model Counting

P. Beame, G. Van den Broeck, E. Gribkoff, D. SuciuCoRR abs/1506.02639, 2014.

Element Distinctness, Frequency Moments, and Sliding Windows

P. Beame, R. Clifford, W. MachmouchiProceedings 54th Annual Symposium on Foundations of Computer ScienceIEEE, 2013.

Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases

P. Beame, J. Li, S. Roy, D. SuciuProceedings 29th Conference on Uncertainty in Artificial Intelligence, 2013.

Communication Steps for Parallel Query Processing

P. Beame, P. Koutris, D. SuciuProceedings of the Thirty-Second Annual ACM Symposium on Principles of Database Systems, 2013.

Element Distinctness, Frequency Moments, and Sliding Windows

P. Beame, R. Clifford, W. MachmouchiCoRR abs/1309.3690, 2013.  Also Technical Report TR13-127, # eccc # available at http://eccc.hpi-web.de/report/2013/127

Communication Steps for Parallel Query Processing

P. Beame, P. Koutris, D. SuciuCoRR abs/1306.5972, 2013.

Model Counting of Query Expressions: Limitations of Propositional Methods

P. Beame, J. Li, S. Roy, D. SuciuCoRR abs/1312.4125, 2013.

Approximating $AC^0$ Circuits by Small Height Decision Trees and a Deterministic Algorithm for $\#AC^0$-SAT

P. Beame, R. Impagliazzo, S. SrinivasanProceedings Twenty-Seventh Annual IEEE Conference on Computational Complexity, 2012.

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

P. Beame, C. Beck, R. ImpagliazzoProceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012.

Sliding Windows with Limited Storage

P. Beame, R. Clifford, W. MachmouchiCoRR abs/1212.4372, 2012.  Also Technical Report TR12-178, # eccc # available at http://eccc.uni-trier.de/eccc-reports/2012/TR12-178/index.html

The Quantum Query Complexity of $AC^0$

P. Beame, W. MachmouchiQuantum Information \& Computation 12:7–8, 2012.

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

P. Beame, T. HuynhSIAM Journal on Computing 41:3, 2012.

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

P. Beame, C. Beck, R. ImpagliazzoElectronic Colloquium in Computational Complexity:TR11-149, 2011.

Making Branching Programs Oblivious Requires Superlogarithmic Overhead

P. Beame, W. MachmouchiProceedings Twenty-Sixth Annual IEEE Conference on Computational Complexity, 2011.

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

P. Beame, T. HuynhACM Transactions on Computation Theory 3:2, 2011.

Hardness Amplification in Proof Complexity

P. Beame, T. Huynh, T. PitassiProceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, 2010.

Formula Caching in DPLL

P. Beame, R. Impagliazzo, T. Pitassi, N. SegerlindACM Transactions on Computation Theory 1:3, 2010.

Separating Deterministic from Randomized Multiparty Communication Complexity

P. Beame, M. David, T. Pitassi, P. WoelfelTheory of Computing 6, 2010.

The Quantum Query Complexity of $AC^0$

P. Beame, W. Machmouchiarxiv/quant-phys:arXiv:1008.2422v1, 2010.

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

P. Beame, D.T. Huynh-NgocProceedings 50th Annual Symposium on Foundations of Computer ScienceIEEE, 2009.

Longest Common Subsequences in Sets of Permutations

P. Beame, E. Blais, D.T. Huynh-Ngocarxiv/math.co:arXiv:0904.1615, 2009.

Hardness Amplification in Proof Complexity

P. Beame, T. Huynh, T. PitassiElectronic Colloquium in Computational Complexity:TR09-072, 2009.

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

P. Beame, D.T. Huynh-NgocProceedings 49th Annual Symposium on Foundations of Computer ScienceIEEE, 2008.

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

P. Beame, D.T. Huynh-NgocElectronic Colloquium in Computational Complexity:TR08-024, 2008.

Multiparty Communication Complexity and Threshold Circuit Complexity of $AC^0$

P. Beame, D.T. Huynh-NgocElectronic Colloquium in Computational Complexity:TR08-082, 2008.

Lower Bounds for Randomized Read/Write Stream Algorithms

P. Beame, T.S. Jayram, A. RudraProceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007.

A dynamic approach for MPE and Weighted MAX-SAT

T. Sang, P. Beame, H. KautzProceedings of the 20th International Joint Conference in Artificial Intelligence (IJCAI), 2007.

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

P. Beame, R. Impagliazzo, A. SabharwalComputational Complexity 16:3, 2007.

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity

P. Beame, M. David, T. Pitassi, P. WoelfelAutomata, Languages, and Programming: 34th International Colloquium, 2007.

Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

P. Beame, T. Pitassi, N. SegerlindSIAM Journal on Computing 37:3, 2007.

Formula Caching in DPLL

P. Beame, R. Impagliazzo, T. Pitassi, N. SegerlindElectronic Colloquium in Computational Complexity:TR06-140, 2006.

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

P. Beame, T. Pitassi, N. Segerlind, A. WigdersonComputational Complexity 15:4, 2006.  Invited submission for special issue on CCC 2005.

Performing Bayesian Inference by Weighted Model Counting.

T. Sang, P. Beame, H. KautzProceedings, AAAI-05: Twentieth National Conference on Artificial IntelligenceAmerican Association for Artificial Intelligence, 2005.

Heuristics for fast exact model counting

T. Sang, P. Beame, H. KautzSATSpringer 3569, 2005.

The Resolution Complexity of Random Graph $k$-Colorability

P. Beame, J. Culberson, D. Mitchell, C. MooreDiscrete Applied Mathematics 153, 2005.

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

P. Beame, T. Pitassi, N. Segerlind, A. WigdersonProceedings Twentieth Annual IEEE Conference on Computational Complexity, 2005.

Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

P. Beame, T. Pitassi, N. SegerlindAutomata, Languages, and Programming: 32nd International Colloquium, 2005.

Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

P. Beame, T. Pitassi, N. SegerlindElectronic Colloquium in Computational Complexity:TR05-053, 2005.

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

D. Achlioptas, P. Beame, M. MolloyJournal of Computer and System Sciences 68:2, 2004.  Special issue of invited papers from STOC 2001 conference

Exponential Bounds for DPLL Below the Satisfiability Threshold

D. Achlioptas, P. Beame, M. MolloyProceedings of the Fifteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2004.

Towards understanding and harnessing the potential of clause learning

P. Beame, H. Kautz, A. SabharwalJournal of Artificial Intelligence Research 22, 2004.  Honorable mention (sole runner up) 2008 IJCAI-JAIR Best Paper Prize

The Resolution Complexity of Random Graph $k$-Colorability

P. Beame, J. Culberson, D. Mitchell, C. MooreElectronic Colloquium in Computational Complexity:TR04-012, 2004.

Combining Component Caching and Clause Learning for Effective Model Counting

T. Sang, F. Bacchus, P. Beame, H. Kautz, T. PitassiSAT 2004, Satisfiability Conference, 2004.

Proof Complexity

P. BeameComputational Complexity TheoryAmerican Mathematical Society 10, 2004.

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

D. Achlioptas, P. Beame, M. MolloyJournal of Computer and System Sciences 68:2, 2004.

Bounded-depth Frege lower bounds for weaker pigeonhole principles

J. Buresh-Oppenheim, P. Beame, T. Pitassi, R. Raz, A. SabharwalSIAM Journal on Computing 34:2, 2004.

On the power of clause learning

P. Beame, H. Kautz, A. SabharwalProceedings of the 18th International Joint Conference in Artificial Intelligence (IJCAI), 2003.

Memoization and DPLL: Formula Caching Proof Systems

P. Beame, R. Impagliazzo, T. Pitassi, N. SegerlindProceedings Eighteenth Annual IEEE Conference on Computational Complexity, 2003.

Time-Space Trade-Off Lower Bounds for Randomized Computation of Decision Problems

P. Beame, M. Saks, X. Sun, E. VeeJournal of the ACM 50:2, 2003.

Using Problem Structure for Efficient Clause Learning

A. Sabharwal, P. Beame, H. KautzProceedings of the Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT 2003), 2003.

Bounded-depth Frege lower bounds for weaker pigeonhole principles

J. Buresh-Oppenheim, P. Beame, T. Pitassi, R. Raz, A. SabharwalProceedings 43rd Annual Symposium on Foundations of Computer ScienceIEEE, 2002.

Optimal Bounds for the Predecessor Problem and Related Problems

P. Beame, F. FichJournal of Computer and System Sciences 65:1, 2002.  Special issue of selected papers from 1999 STOC conference.

Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems

P. Beame, E. VeeProceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002.

The efficiency of resolution and Davis-Putnam procedures

P. Beame, R. Karp, T. Pitassi, M. SaksSIAM Journal on Computing 31:4, 2002.

Bounded-depth Frege lower bounds for weaker pigeonhole principles

J. Buresh-Oppenheim, P. Beame, T. Pitassi, R. Raz, A. SabharwalElectronic Colloquium in Computational Complexity:TR02-023, 2002.

Optimal Bounds for the Predecessor Problem and Related Problems

P. Beame, F. FichJournal of Computer and System Sciences 65:1, 2002.

Time-Space Tradeoffs for Branching Programs

P. Beame, T.S. Jayram, M. SaksJournal of Computer and System Sciences 63:4, 2001.  Special issue of selected papers from 1998 FOCS Conference

A sharp threshold in proof complexity

D. Achlioptas, P. Beame, M. MolloyProceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, 2001.

The Resolution Complexity of the Independent Set Problem in Random Graphs

P. Beame, R. Impagliazzo, A. SabharwalProceedings Sixteenth Annual IEEE Conference on Computational Complexity, 2001.

Optimizing Symbolic Model-Checking for Statecharts

W. Chan, R.J. Anderson, P. Beame, D.J. Jones, D. Notkin, W.E. WarnerIEEE Transactions on Software Engineering 27:2, 2001.  Special section of invited papers from 21st International Conference on Software Engineering

Propositional Proof Complexity: Past, Present, and Future

P. Beame, T. PitassiCurrent Trends in Theoretical Computer Science: Entering the 21st CenturyWorld Scientific Publishing, 2001.

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

P. Beame, M. Saks, X. Sun, E. VeeProceedings 41st Annual Symposium on Foundations of Computer ScienceIEEE, 2000.

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

P. Beame, M. Saks, X. Sun, E. VeeElectronic Colloquium in Computational Complexity:TR00-025, 2000.

Optimal Bounds for the Predecessor Problem

P. Beame, F. FichProceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999.

Decoupling Synchronization from Logic for Efficient Symbolic Model Checking of Statecharts

W. Chan, R.J. Anderson, P. Beame, D.J. Jones, D. Notkin, W.E. WarnerProceedings of the 21st International Conference on Software Engineering, 1999.

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

P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. TompaSIAM Journal on Computing 28:3, 1999.

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

R.J. Anderson, W. Chan, P. Beame, D. NotkinProceedings of the Andrei Ershov Third International Conference on Perspectives of System Informatics, 1999.

Time-Space Tradeoffs for Branching Programs

P. Beame, M. Saks, J.S. ThathacharProceedings 39th Annual Symposium on Foundations of Computer ScienceIEEE, 1998.

Decoupling Synchronization from Logic for Efficient Symbolic Model Checking of Statecharts

W. Chan, R.J. Anderson, P. Beame, D.J. Jones, D. Notkin, W.E. WarnerDepartment of Computer Science and Engineering, University of Washington:UW-CSE-98-09-02, 1998.

Model Checking Large Software Specifications

W. Chan, R.J. Anderson, P. Beame, S. Burns, F. Modugno, D. Notkin, J.D. ReeseIEEE Transactions on Software Engineering 24:7, 1998.  Special section of invited papers from 4th Foundations in Software Engineering Conference

Propositional Proof Complexity: Past, Present, and Future

P. Beame, T. PitassiBulletin of the European Association for Theoretical Computer Science 65, 1998.  The Computational Complexity Column (ed. E. Allender).

On the complexity of unsatisfiability of random $k$-CNF formulas

P. Beame, R. Karp, T. Pitassi, M. SaksProceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998.

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

W. Chan, R.J. Anderson, P. Beame, D. NotkinISSTA 98: Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis, 1998.  Published as \textitSoftware Engineering Notes, 23(2), March 1998

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

W. Chan, R.J. Anderson, P. Beame, D. NotkinDepartment of Computer Science and Engineering, University of Washington:UW-CSE-98-01-03, 1998.

More on the Relative Strength of Counting Principles

P. Beame, S. RiisProof Complexity and Feasible ArithmeticsAmerican Mathematical Society 39, 1998.

Improved Depth Bounds for Small Distance Connectivity

P. Beame, R. Impagliazzo, T. PitassiComputational Complexity 7:4, 1998.

Time-Space Tradeoffs for Branching Programs

P. Beame, M. Saks, J.S. ThathacharElectronic Colloquium in Computational Complexity:TR98-053, 1998.

Proof Complexity and Feasible Arithmetics

Proof Complexity and Feasible ArithmeticsAmerican Mathematical Society 39, 1998.

The Relative Complexity of NP Search Problems

P. Beame, S.A. Cook, J. Edmonds, R. Impagliazzo, T. PitassiJournal of Computer and System Sciences 57, 1998.  Special issue of invited papers from 1995 STOC conference.

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

P. Beame, F.E. Fich, R. SinhaInformation and Computation 138:1, 1997.

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

W. Chan, R.J. Anderson, P. Beame, D. NotkinComputer Aided Verification, 9th International Conference, CAV'97 ProceedingsSpringer-Verlag 1254, 1997.

On Searching Sorted Lists: A Near-Optimal Lower Bound

P. Beame, F. FichDepartment of Computer Science and Engineering, University of Washington:UW-CSE-97-09-02, 1997.

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata

P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. TompaInformation and Computation 130:2, 1996.

Simplified and Improved Resolution Lower Bounds

P. Beame, T. PitassiProceedings 37th Annual Symposium on Foundations of Computer ScienceIEEE, 1996.

Model Checking Large Software Specifications

R.J. Anderson, P. Beame, S. Burns, W. Chan, F. Modugno, D. Notkin, J.D. ReeseProceedings of the 4th ACM SIGSOFT Symposium on the Foundations of Software Engineering, 1996.  Also published as \textitSoftware Engineering Notes, 21(6), November 1996

Model Checking Large Software Specifications

R.J. Anderson, P. Beame, S. Burns, W. Chan, F. Modugno, D. Notkin, J.D. ReeseDepartment of Computer Science and Engineering, University of Washington:TR-96-04-02, 1996.

Lower bounds on Hilbert's Nullstellensatz and propositional proofs

P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi, P. PudlákProc. London Math. Soc. 73:3, 1996.

Parallel Algorithms for Arrangements

R.J. Anderson, P. Beame, E. BrissonAlgorithmica 15:2, 1996.  Special issue of invited papers from 1990 SPAA conference

An Exponential Separation between the Parity Principle and the Pigeonhole Principle

P. Beame, T. PitassiAnnals of Pure and Applied Logic 80, 1996.

Improved Depth Bounds for Small Distance Connectivity

P. Beame, R. Impagliazzo, T. PitassiProceedings 36th Annual Symposium on Foundations of Computer ScienceIEEE, 1995.

The Relative Complexity of NP Search Problems

P. Beame, S.A. Cook, J. Edmonds, R. Impagliazzo, T. PitassiProceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995.

Lower bounds on Hilbert's Nullstellensatz and propositional proofs

P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi, P. PudlákProceedings 35th Annual Symposium on Foundations of Computer ScienceIEEE, 1994.

A Switching Lemma Primer

P. BeameDepartment of Computer Science and Engineering, University of Washington:UW-CSE-95–07–01, 1994.

Communication-Space Tradeoffs for Unrestricted Protocols

P. Beame, M. Tompa, P. YanSIAM Journal on Computing 23:3, 1994.

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

P. Beame, T. Pitassi8th Annual IEEE Symposium on Logic in Computer Science, 1993.

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

P. Beame, T. PitassiDepartment of Computer Science and Engineering, University of Washington:UW-CSE-93-04-07, 1993.

Time-Space Tradeoffs for Undirected Graph Traversal

P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. TompaDepartment of Computer Science and Engineering, University of Washington:UW-CSE-93–02–01, 1993.

Exponential Lower Bounds for the Pigeonhole Principle

T. Pitassi, P. Beame, R. ImpagliazzoComputational Complexity 3:2, 1993.

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

P. Beame, F.E. Fich, R. SinhaProceedings of the 1993 Workshop on Algorithms and Data Structures, 1993.

Exponential Lower Bounds for the Pigeonhole Principle

P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi, P. Pudlák, A. WoodsProceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992.

Randomized versus Nondeterministic Communication Complexity

P. Beame, J. LawryProceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992.

The Complexity of Computing Symmetric Functions using Threshold Circuits

P. Beame, E. Brisson, R.E. LadnerTheoretical Computer Science 100, 1992.

Exponential Lower Bounds for the Pigeonhole Principle

P. Beame, R. Impagliazzo, T. PitassiUniversity of Toronto, Department of Computer Science:TR257/91, 1991.

A General Sequential Time-Space Tradeoff for Finding Unique Elements

P. BeameSIAM Journal on Computing 20:2, 1991.

Time-Space Tradeoffs for Undirected Graph Traversal

P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. TompaProceedings 31st Annual Symposium on Foundations of Computer ScienceIEEE, 1990.

Communication-Space Tradeoffs for Unrestricted Protocols

P. Beame, M. Tompa, P. YanProceedings 31st Annual Symposium on Foundations of Computer ScienceIEEE, 1990.

Low Overhead Parallel Schedules for Task Graphs

R.J. Anderson, P. Beame, W.L. RuzzoProceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures, 1990.

Parallel Algorithms for Arrangements

R.J. Anderson, P. Beame, E. BrissonProceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures, 1990.

Low Overhead Parallel Schedules for Task Graphs

R.J. Anderson, P. Beame, W.L. RuzzoDepartment of Computer Science and Engineering, University of Washington:UW-CSE-90-04-03, 1990.

The Complexity of Computing Symmetric Functions using Threshold Circuits

P. Beame, E. Brisson, R.E. LadnerDepartment of Computer Science and Engineering, University of Washington:UW-CSE-90-01-01, 1990.

Parallel Search for Maximal Independence Given Minimal Dependence

P. Beame, M. LubyProceedings of the First Annual {ACM-SIAM} Symposium on Discrete AlgorithmsACM, 1990.

Communication-Space Tradeoffs for Unrestricted Protocols

P. Beame, M. Tompa, P. YanDepartment of Computer Science and Engineering, University of Washington:UW-CSE-90-01-12, 1990.

Lower Bounds for Recognizing Small Cliques on CRCW PRAM's

P. BeameDiscrete Applied Mathematics 29:1, 1990.  Special issue on the applications of combinatorics to parallel computation

Parallel Algorithms for Arrangements

R.J. Anderson, P. Beame, E. BrissonDepartment of Computer Science and Engineering, University of Washington:UW-CSE-89-12-08, 1989.

Optimal Bounds for Decision Problems on the CRCW PRAM

P. Beame, J. HåstadJournal of the ACM 36:3, 1989.

A General Sequential Time-Space Tradeoff for Finding Unique Elements

P. BeameProceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, 1989.

Distributed Computing on Transitive Networks: The Torus

P. Beame, H. Bodlaender{STACS} 89: 6th Annual Symposium on Theoretical Aspects of Computer ScienceSpringer-Verlag 349, 1989.

Parallel Search for Maximal Independence Given Minimal Dependence

P. Beame, M. LubyInternational Computer Science Institute:TR-89-003, 1989.

A General Sequential Time-Space Tradeoff for Finding Unique Elements

P. BeameDepartment of Computer Science and Engineering, University of Washington:UW-CSE-88-10-04, 1988.

Limits on the Power of Concurrent-Write Parallel Machines

P. BeameInformation and Computation 76:1, 1988.

Distributed Computing on Transitive Networks: The Torus

P. Beame, H. BodlaenderDepartment of Computer Science, University of Utrecht:RUU-CS-88-31, 1988.

Optimal Bounds for Decision Problems on the CRCW PRAM

P. Beame, J. HåstadProceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987.

Lower Bounds for Recognizing Small Cliques on CRCW PRAM's

P. BeameLaboratory for Computer Science, M.I.T.:TM–336, 1987.

Log Depth Circuits for Division and Related Problems

P.W. Beame, S.A. Cook, J.H. HooverSIAM Journal on Computing 15:4, 1986.

Limits on the Power of Concurrent-Write Parallel Machines

P. BeameProceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 1986.

Lower Bounds in Parallel Machine Computation

P.W. BeameUniversity of Toronto, 1986.  Department of Computer Science Technical Report 198/87

Log Depth Circuits for Division and Related Problems

P.W. Beame, S.A. Cook, J.H. Hoover25th Annual Symposium on Foundations of Computer ScienceIEEE, 1984.

Random Routing in Constant Degree Networks

P.W. BeameDepartment of Computer Science, 1982.  Technical Report 161/82