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

Computational complexity, proof complexity and satisfiability

Time-Space Tradeoffs

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

P. Beame, S.Oveis Gharan, X. YangProceedings of the Fiftieth Annual ACM Symposium on Theory of Computing , 2018 .  

Submitted.

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-120Electronic Colloquium in Computational Complexity available at http://eccc.uni-trier.de/eccc-reports/2017/120/index.html

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 .

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 .

Element Distinctness, Frequency Moments, and Sliding Windows

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

Element Distinctness, Frequency Moments, and Sliding Windows

P. Beame, R. Clifford, W. MachmouchiCoRR  abs/1309.3690 , 2013 .  

Also Technical Report TR13-127, Electronic Colloquium in Computational Complexity available at http://eccc.hpi-web.de/report/2013/127

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 .

Sliding Windows with Limited Storage

P. Beame, R. Clifford, W. MachmouchiCoRR  abs/1212.4372 , 2012 .  

Also Technical Report TR12-178, Electronic Colloquium in Computational Complexity available at http://eccc.uni-trier.de/eccc-reports/2012/TR12-178/index.html

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 .

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 .

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 .

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

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 .

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 .

Time-Space Tradeoffs for Branching Programs

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

Time-Space Tradeoffs for Branching Programs

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

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 .

Communication-Space Tradeoffs for Unrestricted Protocols

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

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 .

A General Sequential Time-Space Tradeoff for Finding Unique Elements

P. BeameSIAM Journal on Computing  20 :2 , 1991 : 270-277 .

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 .

Communication-Space Tradeoffs for Unrestricted Protocols

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

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 .

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 .

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 .

Communication Complexity and Data Streams

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.

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 .

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 .

Communication Cost in Parallel Query Processing

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

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 .

Skew in Parallel Query Processing

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

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 .

Communication Steps for Parallel Query Processing

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

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

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

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 .

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 .

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity

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

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 .

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

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

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 , 2007 : 134–145 .

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.

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 .

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 : 1176–1188 .

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 .

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 .

Communication-Space Tradeoffs for Unrestricted Protocols

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

Randomized versus Nondeterministic Communication Complexity

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

Verification of Software and Hardware

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 .

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

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 .

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 .

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

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 Software Engineering Notes, 23(2), mar 1998

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 .

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 Software Engineering Notes, 21(6), nov 1996

Proof Complexity and Satisfiability

Stabbing Planes

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

To appear.

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).

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 Electronic Colloquium in Computational Complexity available at http://eccc.uni-trier.de/eccc-reports/2017/151/index.html

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 .

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 .

New Limits for Knowledge Compilation and Applications to Exact Model Counting

P. Beame, V. LiewCoRR  abs/1506.02639 , 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 : 2608–2615 .

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 .

Symmetric Weighted First-Order Model Counting

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

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 .

Model Counting of Query Expressions: Limitations of Propositional Methods

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

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 .

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

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

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 .

Hardness Amplification in Proof Complexity

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

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 .

Formula Caching in DPLL

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

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 .

The Resolution Complexity of Random Graph $k$-Colorability

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

Heuristics for fast exact model counting

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

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 .

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 : 1176–1188 .

Proof Complexity

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

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

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 .

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

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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.

More on the Relative Strength of Counting Principles

P. Beame, S. RiisProof Complexity and Feasible ArithmeticsAmerican Mathematical Society  39 , 1998 : 13-35 .

Simplified and Improved Resolution Lower Bounds

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

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\'\iček, T. Pitassi, P. PudlákProc. London Math. Soc.  73 :3 , 1996 : 1–26 .

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 .

Lower bounds on Hilbert's Nullstellensatz and propositional proofs

P. Beame, R. Impagliazzo, J. Kraj\'\iček, T. Pitassi, P. PudlákProceedings 35th Annual Symposium on Foundations of Computer ScienceIEEE , 1994 : 794-806 .

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 .

Exponential Lower Bounds for the Pigeonhole Principle

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

Exponential Lower Bounds for the Pigeonhole Principle

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

Exponential Lower Bounds for the Pigeonhole Principle

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

Parallel and Distributed Computing

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.

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 .

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. SegoufinCoRR  abs/1608.01932 , 2016 .

Communication Cost in Parallel Query Processing

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

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 .

Skew in Parallel Query Processing

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

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 .

Communication Steps for Parallel Query Processing

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

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

Information Broadcasting by Exclusive Read PRAMs

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

The Complexity of Computing Symmetric Functions using Threshold Circuits

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

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 .

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 .

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 .

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

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. RuzzoDepartment of Computer Science and Engineering, University of Washington :UW-CSE-90-04-03 , 1990 .

Distributed Computing on Transitive Networks: The Torus

P. Beame, H. BodlaenderSTACS 89: 6th Annual Symposium on Theoretical Aspects of Computer ScienceSpringer-Verlag  349 , 1989 : 294-303 .

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 .

Parallel Search for Maximal Independence Given Minimal Dependence

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

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 .

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 .

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

Random Routing in Constant Degree Networks

P.W. BeameDepartment of Computer Science, University of Toronto , 1982 .  

Technical Report 161/82

Data Structures

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 .

Optimal Bounds for the Predecessor Problem

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

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 .

Circuit and PRAM Lower Bounds

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

P. Beame, N. Grosshans, P. McKenzie, L. SegoufinCoRR  abs/1608.01932 , 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 : 5:1–5:34 .

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 .

The Quantum Query Complexity of $AC^0$

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

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

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

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

Improved Depth Bounds for Small Distance Connectivity

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

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 .

Improved Depth Bounds for Small Distance Connectivity

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

A Switching Lemma Primer

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

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 .

The Complexity of Computing Symmetric Functions using Threshold Circuits

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

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

Optimal Bounds for Decision Problems on the CRCW PRAM

P. Beame, J. H\aastadJournal of the ACM  36 :3 , 1989 : 643-670 .

Limits on the Power of Concurrent-Write Parallel Machines

P. BeameInformation and Computation  76 :1 , 1988 : 13-28 .

Optimal Bounds for Decision Problems on the CRCW PRAM

P. Beame, J. H\aastadProceedings 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 .

Lower Bounds in Parallel Machine Computation

P.W. BeameUniversity of Toronto , 1986 .  

Department of Computer Science Technical Report 198/87

Limits on the Power of Concurrent-Write Parallel Machines

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

Other topics

Edge Estimation with Independent Set Oracles

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

To appear.

The Quantum Query Complexity of $AC^0$

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

The Quantum Query Complexity of $AC^0$

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

Longest Common Subsequences in Sets of Permutations

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

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.

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 .

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

P. Beame, P. MuirBIT  29 , 1989 : 126-139 .