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

Computational complexity, proof complexity and satisfiability

2018

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.

 

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.

 

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.

 

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 .
 

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

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

2016

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

P. Beame, C. RashtchianCoRR  abs/1611.04999 , 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. SegoufinCoRR  abs/1608.01932 , 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 .
 

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 .
 

Communication Cost in Parallel Query Processing

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

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 .
 

New Limits for Knowledge Compilation and Applications to Exact Model Counting

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

Finding the Median (Obliviously) with Bounded Space

P. Beame, V. Liew, M. 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 .
 

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 .
 

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 .
 

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

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 .
 

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 .
 

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

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 .
 

A Note on Neciporuk's Method for Nondeterministic Branching Programs

P. Beame, P. McKenzie , 2011 .  

Draft

 

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 Nondeterministic NOF 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 .
 

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 .
 

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 .
 

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 .
 

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

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

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 , 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

Proof Complexity

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

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 .
 

The Resolution Complexity of Random Graph $k$-Colorability

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

Combining Component Caching and Clause Learning for Effective Model Counting

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

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 .
 

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

 

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 .
 

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 .
 

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 .
 

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 .
 

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 .
 

Bounded-depth Frege lower bounds for weaker pigeonhole principles

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

Optimal Bounds for the Predecessor Problem and Related Problems

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

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

 

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 .
 

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

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 .
 

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 .
 

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 .
 

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

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 .
 

More on the Relative Strength of Counting Principles

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

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.

 

Improved Depth Bounds for Small Distance Connectivity

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

Time-Space Tradeoffs for Branching Programs

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

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 Software Engineering Notes, 21(6), nov 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\'\ič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\'\iček, T. Pitassi, P. PudlákProceedings 35th Annual Symposium on Foundations of Computer ScienceIEEE , 1994 : 794-806 .
 

Information Broadcasting by Exclusive Read PRAMs

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

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 .
 

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

Randomized versus Nondeterministic Communication Complexity

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

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 .
 

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

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 .
 

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 .
 

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 .
 

Parallel Algorithms for Arrangements

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

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

 

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 .
 

1989

Optimal Bounds for Decision Problems on the CRCW PRAM

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

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

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

1988

Limits on the Power of Concurrent-Write Parallel Machines

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

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 .
 

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

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, University of Toronto , 1982 .  

Technical Report 161/82