Contact

Paul Beame
CSE 668
206-543-5114
beamecs.washington.edu
Theory of Computation
Areas of interest: 

Computational complexity, proof complexity and satisfiability

Quantum Time-Space Tradeoffs for Matrix Problems

P. Beame, N. Kornerup, M. Whitmeyer, Proceedings of the Fifty-Sixth Annual ACM Symposium on Theory of Computing, 2024.

Quantum Time-Space Tradeoffs for Matrix Problems

P. Beame, N. Kornerup, M. Whitmeyer, CoRR abs/2401.05321, 2024.
Arxiv: http://arxiv.org/abs/2401.05321v2 also Electronic Colloquium on Computational Complexity (ECCC) TR24-011: http://eccc.weizmann.acl.il/report/2024/011/#revision1

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

P. Beame, S. Koroth, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10–13, 2023, Cambridge, MA, USA, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 251, 2023.

Towards a Complexity Theory of Parallel Computation

P. Beame, P. McKenzie, Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook, Association for Computing Machinery, 2023.

Cumulative Memory Lower Bounds for Randomized and Quantum Computation

P. Beame, N. Kornerup, Automata, Languages, and Programming: 50th International Colloquium (ICALP 2023), 2023.

Cumulative Memory Lower Bounds for Randomized and Quantum Computation

P. Beame, N. Kornerup, CoRR abs/2301.05680, 2023.
Arxiv: http://arxiv.org/abs/2301.05680 also Electronic Colloquium on Computational Complexity (ECCC) TR23-005: http://eccc.weizmann.acl.il/report/2023/005/

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

P. Beame, S. Koroth, CoRR abs/2211.17211, 2022.
http://arxiv.org/abs/2211.17211 Arxiv http://eccc.weizmann.ac.il/report/2022/173/index.html ECCC Technical Report TR22-173

Adding Dual Variables to Algebraic Reasoning for Circuit Verification

D. Kaufmann, P. Beame, A. Biere, J. Nordström, Proceedings of 25th Design, Automation and Test in Europe (DATE), IEEE, 2022.

Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning

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

Edge Estimation with Independent Set Oracles

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

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

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

Technical perspective: Two for the price of one

P. Beame, Communications of the ACM 63:10, 2020.

Toward Verifying Nonlinear Integer Arithmetic

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

Smoothing Structured Decomposable Circuits

A. Shih, G. Van den Broeck, P. Beame, A. Amarilli, Advances 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. Amarilli, CoRR abs/1906.00311, 2019.

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

P. Beame, S.Oveis Gharan, X. Yang, Proceedings 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. Sinha, Proceedings 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. Robere, Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 94, 2018.

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

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

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

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

Communication Steps for Parallel Query Processing

P. Beame, P. Koutris, D. Suciu, Journal 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. Liew, Computer Aided Verification, 29th International Conference, CAV'17 Proceedings, Part II, 2017.

Towards Verifying Nonlinear Integer Arithmetic

P. Beame, V. Liew, CoRR abs/1705.04302, 2017.

Exact Model Counting of Query Expressions: Limitations of Propositional Methods

P. Beame, J. Li, S. Roy, D. Suciu, ACM 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. Rashtchian, Proceedings of the Twenty-Eighth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2017.

Stabbing Planes

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

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

P. Beame, S.Oveis Gharan, X. Yang, CoRR 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
http://arxiv.org/abs/1708.02640 Arxiv http://eccc.uni-trier.de/eccc-reports/2017/120/index.html ECCC Technical Report TR17-120

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

P. Beame, C. Rashtchian, CoRR abs/1611.04999, 2016.

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

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

Worst-Case Optimal Algorithms for Parallel Query Processing

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

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

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

Worst-Case Optimal Algorithms for Parallel Query Processing

P. Beame, P. Koutris, D. Suciu, CoRR abs/1604.01848, 2016.

Communication Cost in Parallel Query Processing

P. Beame, P. Koutris, D. Suciu, CoRR abs/1602.06236, 2016.

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

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

New Limits for Knowledge Compilation and Applications to Exact Model Counting

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

Symmetric Weighted First-Order Model Counting

P. Beame, G. Van den Broeck, E. Gribkoff, D. Suciu, Proceedings 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. Patrascu, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 2015.

Finding the Median (Obliviously) with Bounded Space

P. Beame, V. Liew, M. Patrascu, CoRR abs/1505.00090, 2015.

New Limits for Knowledge Compilation and Applications to Exact Model Counting

P. Beame, V. Liew, CoRR abs/1506.02639, 2015.

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

P. Beame, A. Sabharwal, Proceedings, AAAI-14: Twenty-Eighth National Conference on Artificial Intelligence, American Association for Artificial Intelligence, 2014.

Skew in Parallel Query Processing

P. Beame, P. Koutris, D. Suciu, Proceedings 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. Suciu, Proceedings of 17th International Conference on Database Theory, 2014.

Skew in Parallel Query Processing

P. Beame, P. Koutris, D. Suciu, CoRR abs/1401.1872, 2014.

Symmetric Weighted First-Order Model Counting

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

Element Distinctness, Frequency Moments, and Sliding Windows

P. Beame, R. Clifford, W. Machmouchi, Proceedings 54th Annual Symposium on Foundations of Computer Science, IEEE, 2013.

Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases

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

Communication Steps for Parallel Query Processing

P. Beame, P. Koutris, D. Suciu, Proceedings of the Thirty-Second Annual ACM Symposium on Principles of Database Systems, 2013.  Winner of 2023 ACM PODS Alberto O. Mendelzon Test-of-Time Award.

Element Distinctness, Frequency Moments, and Sliding Windows

P. Beame, R. Clifford, W. Machmouchi, CoRR abs/1309.3690, 2013.  Also Technical Report TR13-127, # eccc # available at http://eccc.hpi-web.de/report/2013/127
http://arxiv.org/abs/1309.3690 Arxiv http://eccc.hpi-web.de/report/2013/127 ECCC Technical Report TR13-127

Communication Steps for Parallel Query Processing

P. Beame, P. Koutris, D. Suciu, CoRR abs/1306.5972, 2013.

Model Counting of Query Expressions: Limitations of Propositional Methods

P. Beame, J. Li, S. Roy, D. Suciu, CoRR 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. Srinivasan, Proceedings 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. Impagliazzo, Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012.

Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear space

P. Beame, C. Beck, R. Impagliazzo, STOC, 2012.
http://www.cs.washington.edu/homes/beame/papers/proofspaceeccc.pdf

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

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

The Quantum Query Complexity of $AC^0$

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

Sliding Windows with Limited Storage

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

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

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

Making Branching Programs Oblivious Requires Superlogarithmic Overhead

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

On the value of multiple read/write streams for approximating frequency moments

P. Beame, T. Huynh, ACM Transactions on Computation Theory, 2011.
http://www.cs.washington.edu/homes/beame/papers/freqjournal.pdf

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

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

A Note on Neciporuk's Method for Nondeterministic Branching Programs

P. Beame, P. McKenzie, 2011.

Hardness Amplification in Proof Complexity

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

Formula Caching in DPLL

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

Separating Deterministic from Randomized Multiparty Communication Complexity

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

The Quantum Query Complexity of $AC^0$

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

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

P. Beame, D.T. Huynh-Ngoc, Proceedings 50th Annual Symposium on Foundations of Computer Science, IEEE, 2009.

Longest Common Subsequences in Sets of Permutations

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

Hardness Amplification in Proof Complexity

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

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

P. Beame, D.T. Huynh-Ngoc, Proceedings 49th Annual Symposium on Foundations of Computer Science, IEEE, 2008.

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

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

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

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

Lower Bounds for Randomized Read/Write Stream Algorithms

P. Beame, T.S. Jayram, A. Rudra, Proceedings 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. Kautz, Proceedings 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. Sabharwal, Computational Complexity 16:3, 2007.

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

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

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity

P. Beame, M. David, T. Pitassi, P. Woelfel, Automata, Languages, and Programming: 34th International Colloquium (ICALP 2007), 2007.

Formula Caching in DPLL

P. Beame, R. Impagliazzo, T. Pitassi, N. Segerlind, Electronic 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. Wigderson, Computational Complexity 15:4, 2006.  Invited submission for special issue on CCC 2005.

Performing Bayesian Inference by Weighted Model Counting.

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

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

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

The Resolution Complexity of Random Graph $k$-Colorability

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

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

P. Beame, T. Pitassi, N. Segerlind, Automata, Languages, and Programming: 32nd International Colloquium (ICALP 2005), 2005.

Heuristics for fast exact model counting

T. Sang, P. Beame, H. Kautz, SAT, Springer 3569, 2005.

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

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

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

D. Achlioptas, P. Beame, M. Molloy, Journal 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. Molloy, Proceedings of the Fifteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2004.

The Resolution Complexity of Random Graph $k$-Colorability

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

Towards understanding and harnessing the potential of clause learning

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

Proof Complexity

P. Beame, Computational Complexity Theory, American Mathematical Society 10, 2004.

Combining Component Caching and Clause Learning for Effective Model Counting

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

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

D. Achlioptas, P. Beame, M. Molloy, Journal 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. Sabharwal, SIAM Journal on Computing 34:2, 2004.

On the power of clause learning

P. Beame, H. Kautz, A. Sabharwal, Proceedings 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. Segerlind, Proceedings 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. Vee, Journal of the ACM 50:2, 2003.

Using Problem Structure for Efficient Clause Learning

A. Sabharwal, P. Beame, H. Kautz, Proceedings 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. Sabharwal, Proceedings 43rd Annual Symposium on Foundations of Computer Science, IEEE, 2002.

Optimal Bounds for the Predecessor Problem and Related Problems

P. Beame, F. Fich, Journal 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. Vee, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002.

Optimal Bounds for the Predecessor Problem and Related Problems

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

Bounded-depth Frege lower bounds for weaker pigeonhole principles

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

The efficiency of resolution and Davis-Putnam procedures

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

Time-Space Tradeoffs for Branching Programs

P. Beame, T.S. Jayram, M. Saks, Journal 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. Molloy, Proceedings 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. Sabharwal, Proceedings Sixteenth Annual IEEE Conference on Computational Complexity, 2001.

Propositional Proof Complexity: Past, Present, and Future

P. Beame, T. Pitassi, Current Trends in Theoretical Computer Science: Entering the 21st Century, World Scientific Publishing, 2001.

Optimizing Symbolic Model-Checking for Statecharts

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

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

P. Beame, M. Saks, X. Sun, E. Vee, Proceedings 41st Annual Symposium on Foundations of Computer Science, IEEE, 2000.

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

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

Optimal Bounds for the Predecessor Problem

P. Beame, F. Fich, Proceedings 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. Warner, Proceedings 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. Tompa, SIAM 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. Notkin, Proceedings 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. Thathachar, Proceedings 39th Annual Symposium on Foundations of Computer Science, IEEE, 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. Warner, Department 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. Reese, IEEE 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. Pitassi, Bulletin 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. Saks, Proceedings 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. Notkin, ISSTA 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. Notkin, Department 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. Riis, Proof Complexity and Feasible Arithmetics, American Mathematical Society 39, 1998.

Time-Space Tradeoffs for Branching Programs

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

Improved Depth Bounds for Small Distance Connectivity

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

Proof Complexity and Feasible Arithmetics

, Proof Complexity and Feasible Arithmetics, American Mathematical Society 39, 1998.

The Relative Complexity of NP Search Problems

P. Beame, S.A. Cook, J. Edmonds, R. Impagliazzo, T. Pitassi, Journal 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. Sinha, Information 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. Notkin, Computer Aided Verification, 9th International Conference, CAV'97 Proceedings, Springer-Verlag 1254, 1997.

On Searching Sorted Lists: A Near-Optimal Lower Bound

P. Beame, F. Fich, Department 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. Tompa, Information and Computation 130:2, 1996.

Model Checking Large Software Specifications

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

Simplified and Improved Resolution Lower Bounds

P. Beame, T. Pitassi, Proceedings 37th Annual Symposium on Foundations of Computer Science, IEEE, 1996.

Model Checking Large Software Specifications

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

Parallel Algorithms for Arrangements

R.J. Anderson, P. Beame, E. Brisson, Algorithmica 15:2, 1996.  Special issue of invited papers from 1990 SPAA conference
http://www.cs.washington.edu/homes/beame/papers/arrangejournal.pdf preprint http://link.springer.com/article/10.1007%2FBF01941684 journal link

An Exponential Separation between the Parity Principle and the Pigeonhole Principle

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

Lower bounds on Hilbert's Nullstellensatz and propositional proofs

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

Improved Depth Bounds for Small Distance Connectivity

P. Beame, R. Impagliazzo, T. Pitassi, Proceedings 36th Annual Symposium on Foundations of Computer Science, IEEE, 1995.

The Relative Complexity of NP Search Problems

P. Beame, S.A. Cook, J. Edmonds, R. Impagliazzo, T. Pitassi, Proceedings 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ák, Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994.

A Switching Lemma Primer

P. Beame, Department 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. Yan, SIAM Journal on Computing 23:3, 1994.

Information Broadcasting by Exclusive Read PRAMs

P. Beame, M. Kik, M. Kutyłowski, Parallel Processing Letters 4:1&2, 1994.
http://www.cs.washington.edu/homes/beame/papers/broadcast.ps preprint http://www.worldscientific.com/doi/abs/10.1142/S012962649400017X journal link

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

P. Beame, T. Pitassi, 8th Annual IEEE Symposium on Logic in Computer Science, 1993.

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

P. Beame, T. Pitassi, Department 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. Tompa, Department 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. Impagliazzo, Computational Complexity 3:2, 1993.

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

P. Beame, F.E. Fich, R. Sinha, Proceedings of the 1993 Workshop on Algorithms and Data Structures, 1993.
http://www.cs.washington.edu/homes/beame/papers/crew.ps preprint http://link.springer.com/chapter/10.1007%2F3-540-57155-8_245 conference proceedings

Exponential Lower Bounds for the Pigeonhole Principle

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

Randomized versus Nondeterministic Communication Complexity

P. Beame, J. Lawry, Proceedings 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. Ladner, Theoretical Computer Science 100, 1992.

Exponential Lower Bounds for the Pigeonhole Principle

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

A General Sequential Time-Space Tradeoff for Finding Unique Elements

P. Beame, SIAM Journal on Computing 20:2, 1991.

Communication-Space Tradeoffs for Unrestricted Protocols

P. Beame, M. Tompa, P. Yan, Proceedings 31st Annual Symposium on Foundations of Computer Science, IEEE, 1990.

Time-Space Tradeoffs for Undirected Graph Traversal

P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. Tompa, Proceedings 31st Annual Symposium on Foundations of Computer Science, IEEE, 1990.

Parallel Algorithms for Arrangements

R.J. Anderson, P. Beame, E. Brisson, Proceedings 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. Ruzzo, Proceedings 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. Ruzzo, Department 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. Ladner, Department 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. Luby, Proceedings of the First Annual {ACM-SIAM} Symposium on Discrete Algorithms, ACM, 1990.

Communication-Space Tradeoffs for Unrestricted Protocols

P. Beame, M. Tompa, P. Yan, Department 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. Beame, Discrete 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. Brisson, Department 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åstad, Journal of the ACM 36:3, 1989.

A General Sequential Time-Space Tradeoff for Finding Unique Elements

P. Beame, Proceedings 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 Science, Springer-Verlag 349, 1989.
http://www.cs.washington.edu/homes/beame/papers/grid.ps preprint http://link.springer.com/chapter/10.1007%2FBFb0028993 conference proceedings link

Parallel Search for Maximal Independence Given Minimal Dependence

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

On Error Expressions for Reflected and Averaged Implicit Runge-Kutta Methods

P. Beame, P. Muir, BIT 29, 1989.

A General Sequential Time-Space Tradeoff for Finding Unique Elements

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

Limits on the Power of Concurrent-Write Parallel Machines

P. Beame, Information and Computation 76:1, 1988.

Distributed Computing on Transitive Networks: The Torus

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

Optimal Bounds for Decision Problems on the CRCW PRAM

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

Lower Bounds for Recognizing Small Cliques on CRCW PRAM's

P. Beame, Laboratory 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. Hoover, SIAM Journal on Computing 15:4, 1986.

Limits on the Power of Concurrent-Write Parallel Machines

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

Lower Bounds in Parallel Machine Computation

P.W. Beame, University 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. Hoover, 25th Annual Symposium on Foundations of Computer Science, IEEE, 1984.

Random Routing in Constant Degree Networks

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