Contact

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

Computational complexity, proof complexity and satisfiability

2024

Quantum Time-Space Tradeoffs for Matrix Problems

P. Beame, N. Kornerup, M. WhitmeyerProceedings of the Fifty-Sixth Annual ACM Symposium on Theory of Computing, 2024. To appear
 

Quantum Time-Space Tradeoffs for Matrix Problems

P. Beame, N. Kornerup, M. WhitmeyerCoRR 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

2023

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

P. Beame, S. Koroth14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10–13, 2023, Cambridge, MA, USASchloss Dagstuhl - Leibniz-Zentrum für Informatik 251, 2023: 14:1-14:17.
 

Towards a Complexity Theory of Parallel Computation

P. Beame, P. McKenzieLogic, Automata, and Computational Complexity: The Works of Stephen A. CookAssociation for Computing Machinery, 2023: 107–126.
 

Cumulative Memory Lower Bounds for Randomized and Quantum Computation

P. Beame, N. KornerupCoRR 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/

Cumulative Memory Lower Bounds for Randomized and Quantum Computation

P. Beame, N. KornerupAutomata, Languages, and Programming: 50th International Colloquium (ICALP 2023), 2023: 17:1-17:20.
 

2022

Adding Dual Variables to Algebraic Reasoning for Circuit Verification

D. Kaufmann, P. Beame, A. Biere, J. NordströmProceedings of 25th Design, Automation and Test in Europe (DATE)IEEE, 2022: 1435–1440.
 

2020

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: 194–204.
 

Edge Estimation with Independent Set Oracles

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

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: 1232–1247.
 

Technical perspective: Two for the price of one

P. BeameCommunications of the ACM 63:10, 2020: 96.
 

2019

Toward Verifying Nonlinear Integer Arithmetic

P. Beame, V. LiewJournal of the ACM 66:3, 2019: 22:1-30.
 

Smoothing Structured Decomposable Circuits

A. Shih, G. Van den Broeck, P. Beame, A. AmarilliCoRR abs/1906.00311, 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: 11412–11422.
 

2018

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: 843–856.
 

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: 38:1–38:21.
 

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: 10:1–10:20.
 

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

P. Beame, S.Oveis Gharan, X. YangCoRR abs/1806.06973, 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.
 

2017

Communication Steps for Parallel Query Processing

P. Beame, P. Koutris, D. SuciuJournal of the ACM 64:6, 2017: 40:1-58. 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: 238–258.
 

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: 1:1–45. 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: 289–306.
 

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

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

2016

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: 8:1–8:18.
 

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: 5:1–5:34.
 

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.
 

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

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

2015

New Limits for Knowledge Compilation and Applications to Exact Model Counting

P. Beame, V. LiewProceedings 31st Conference on Uncertainty in Artificial Intelligence, 2015: 131–140.
 

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: 313–328.
 

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: 103–115.
 

Finding the Median (Obliviously) with Bounded Space

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

New Limits for Knowledge Compilation and Applications to Exact Model Counting

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

2014

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: 2608–2615.
 

Skew in Parallel Query Processing

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

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: 177–188.
 

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.
 

2013

Element Distinctness, Frequency Moments, and Sliding Windows

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

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: 52–61.
 

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: 273–284. Winner of 2023 ACM PODS Alberto O. Mendelzon Test-of-Time Award.
 

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.
 

2012

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: 117–125.
 

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: 212–232.
 

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

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

The Quantum Query Complexity of $AC^0$

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

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

2011

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: 12–22.
 

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

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

2010

Hardness Amplification in Proof Complexity

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

Formula Caching in DPLL

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

Separating Deterministic from Randomized Multiparty Communication Complexity

P. Beame, M. David, T. Pitassi, P. WoelfelTheory of Computing 6, 2010: 201–225.
 

The Quantum Query Complexity of $AC^0$

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

2009

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: 53–62.
 

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.
 

2008

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: 499–508.
 

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

P. Beame, D.T. Huynh-NgocElectronic Colloquium in Computational Complexity:TR08-082, 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.
 

2007

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: 689–698.
 

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: 173–179.
 

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

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

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: 845–869.
 

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity

P. Beame, M. David, T. Pitassi, P. WoelfelAutomata, Languages, and Programming: 34th International Colloquium (ICALP 2007), 2007: 134–145.
 

2006

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: 391–432. Invited submission for special issue on CCC 2005.
 

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: 475-482.
 

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.
 

The Resolution Complexity of Random Graph $k$-Colorability

P. Beame, J. Culberson, D. Mitchell, C. MooreDiscrete Applied Mathematics 153, 2005: 25–47.
 

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 (ICALP 2005), 2005: 1176–1188.
 

Heuristics for fast exact model counting

T. Sang, P. Beame, H. KautzSATSpringer 3569, 2005: 226–240.
 

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: 52–66.
 

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: 238–268. 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: 139–140.
 

The Resolution Complexity of Random Graph $k$-Colorability

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

Towards understanding and harnessing the potential of clause learning

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

Proof Complexity

P. BeameComputational Complexity TheoryAmerican Mathematical Society 10, 2004: 199–246.
 

Combining Component Caching and Clause Learning for Effective Model Counting

T. Sang, F. Bacchus, P. Beame, H. Kautz, T. PitassiSAT 2004, Satisfiability Conference, 2004: 20–28.
 

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: 238–268.
 

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: 261–276.
 

2003

On the power of clause learning

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

Memoization and DPLL: Formula Caching Proof Systems

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

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: 154–195.
 

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: 159–166.
 

2002

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: 583–592.
 

Optimal Bounds for the Predecessor Problem and Related Problems

P. Beame, F. FichJournal of Computer and System Sciences 65:1, 2002: 38–72. 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: 688-697.
 

Optimal Bounds for the Predecessor Problem and Related Problems

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

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.
 

The efficiency of resolution and Davis-Putnam procedures

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

2001

Time-Space Tradeoffs for Branching Programs

P. Beame, T.S. Jayram, M. SaksJournal of Computer and System Sciences 63:4, 2001: 542–572. 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: 337–346.
 

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: 52-68.
 

Propositional Proof Complexity: Past, Present, and Future

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

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: 170–190. Special section of invited papers from 21st International Conference on Software Engineering
 

2000

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: 169–179.
 

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.
 

1999

Optimal Bounds for the Predecessor Problem

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

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: 142–151.
 

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: 1051–1072.
 

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: 355-361.
 

1998

Time-Space Tradeoffs for Branching Programs

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

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: 498–520. 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: 561-571.
 

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: 102–112. 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: 13-35.
 

Time-Space Tradeoffs for Branching Programs

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

Improved Depth Bounds for Small Distance Connectivity

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

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: 3–19. Special issue of invited papers from 1995 STOC conference.
 

1997

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

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

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: 316–327.
 

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.
 

1996

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: 101-129.
 

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: 156–166. Also published as \textitSoftware Engineering Notes, 21(6), November 1996
 

Simplified and Improved Resolution Lower Bounds

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

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.
 

Parallel Algorithms for Arrangements

R.J. Anderson, P. Beame, E. BrissonAlgorithmica 15:2, 1996: 104-125. 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: 197-222.
 

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: 1–26.
 

1995

Improved Depth Bounds for Small Distance Connectivity

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

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: 303–314.
 

1994

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: 794-806.
 

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: 652-661.
 

Information Broadcasting by Exclusive Read PRAMs

P. Beame, M. Kik, M. KutyłowskiParallel Processing Letters 4:1&2, 1994: 159-169.

1993

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

P. Beame, T. Pitassi8th Annual IEEE Symposium on Logic in Computer Science, 1993: 308–319.
 

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: 97–140.
 

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: 163-174.

1992

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: 200-220.
 

Randomized versus Nondeterministic Communication Complexity

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

The Complexity of Computing Symmetric Functions using Threshold Circuits

P. Beame, E. Brisson, R.E. LadnerTheoretical Computer Science 100, 1992: 253-265.
 

1991

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: 270-277.
 

1990

Communication-Space Tradeoffs for Unrestricted Protocols

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

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: 429-438.
 

Parallel Algorithms for Arrangements

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

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: 66-75.
 

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: 212-218.
 

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: 3-20. Special issue on the applications of combinatorics to parallel computation
 

1989

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: 643-670.
 

A General Sequential Time-Space Tradeoff for Finding Unique Elements

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

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: 294-303.

Parallel Search for Maximal Independence Given Minimal Dependence

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

1988

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: 13-28.
 

Distributed Computing on Transitive Networks: The Torus

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

1987

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: 83-93.
 

Lower Bounds for Recognizing Small Cliques on CRCW PRAM's

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

1986

Log Depth Circuits for Division and Related Problems

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

Limits on the Power of Concurrent-Write Parallel Machines

P. BeameProceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 1986: 169-176.
 

Lower Bounds in Parallel Machine Computation

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

1984

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: 1-6.
 

1982

Random Routing in Constant Degree Networks

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