Time-Space Tradeoffs
Quantum Time-Space Tradeoffs for Matrix Problems
P. Beame, N. Kornerup, M. Whitmeyer, Proceedings of the Fifty-Sixth Annual ACM Symposium on Theory of Computing, 2024 : 596–607.
Quantum Time-Space Tradeoffs for Matrix Problems
P. Beame, N. Kornerup, M. Whitmeyer, CoRR abs/2401.05321, 2024 .
Arxiv: http://arxiv.org/abs/2401.05321v2 also Electronic Colloquium on Computational Complexity (ECCC) TR24-011: http://eccc.weizmann.acl.il/report/2024/011/#revision1
Cumulative Memory Lower Bounds for Randomized and Quantum Computation
P. Beame, N. Kornerup, Automata, Languages, and Programming: 50th International Colloquium (ICALP 2023), 2023 : 17:1-17:20.
Cumulative Memory Lower Bounds for Randomized and Quantum Computation
P. Beame, N. Kornerup, CoRR abs/2301.05680, 2023 .
Arxiv: http://arxiv.org/abs/2301.05680 also Electronic Colloquium on Computational Complexity (ECCC) TR23-005: http://eccc.weizmann.acl.il/report/2023/005/
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials
P. Beame, S.Oveis Gharan, X. Yang, Proceedings of the 31st Conference on Learning Theory, COLT 2018, 2018 : 843–856.
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials
P. Beame, S.Oveis Gharan, X. Yang, Electronic Colloquium in Computational Complexity:TR18-114, 2018 .
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
P. Beame, S.Oveis Gharan, X. Yang, CoRR abs/1708.02640, 2017 . Also July 2017 Technical Report TR17-120 # eccc # available at http://eccc.uni-trier.de/eccc-reports/2017/120/index.html
http://arxiv.org/abs/1708.02640 Arxiv http://eccc.uni-trier.de/eccc-reports/2017/120/index.html ECCC Technical Report TR17-120
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
P. Beame, C. Beck, R. Impagliazzo, SIAM Journal on Computing 45:4, 2016 : 1612–1645.
Finding the Median (Obliviously) with Bounded Space
P. Beame, V. Liew, M. Patrascu, Automata, Languages, and Programming – 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 2015 : 103–115.
Finding the Median (Obliviously) with Bounded Space
P. Beame, V. Liew, M. Patrascu, CoRR abs/1505.00090, 2015 .
Element Distinctness, Frequency Moments, and Sliding Windows
P. Beame, R. Clifford, W. Machmouchi, Proceedings 54th Annual Symposium on Foundations of Computer Science, IEEE, 2013 : 290–299.
Element Distinctness, Frequency Moments, and Sliding Windows
P. Beame, R. Clifford, W. Machmouchi, CoRR abs/1309.3690, 2013 . Also Technical Report TR13-127, # eccc # available at http://eccc.hpi-web.de/report/2013/127
http://arxiv.org/abs/1309.3690 Arxiv http://eccc.hpi-web.de/report/2013/127 ECCC Technical Report TR13-127
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
P. Beame, C. Beck, R. Impagliazzo, Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012 : 212–232.
Sliding Windows with Limited Storage
P. Beame, R. Clifford, W. Machmouchi, CoRR abs/1212.4372, 2012 . Also Technical Report TR12-178, # eccc # available at http://eccc.uni-trier.de/eccc-reports/2012/TR12-178/index.html
http://arxiv.org/abs/1212.4372 Arxiv http://eccc.uni-trier.de/eccc-reports/2012/TR12-178/index.html ECCC Technical Report TR12-178
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
P. Beame, C. Beck, R. Impagliazzo, Electronic Colloquium in Computational Complexity:TR11-149, 2011 .
Making Branching Programs Oblivious Requires Superlogarithmic Overhead
P. Beame, W. Machmouchi, Proceedings Twenty-Sixth Annual IEEE Conference on Computational Complexity, 2011 : 12–22.
Time-Space Trade-Off Lower Bounds for Randomized Computation of Decision Problems
P. Beame, M. Saks, X. Sun, E. Vee, Journal of the ACM 50:2, 2003 : 154–195.
Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems
P. Beame, E. Vee, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002 : 688-697.
Time-Space Tradeoffs for Branching Programs
P. Beame, T.S. Jayram, M. Saks, Journal 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. Vee, Proceedings 41st Annual Symposium on Foundations of Computer Science, IEEE, 2000 : 169–179.
Super-linear Time-Space Tradeoff Lower Bounds for Randomized Computation
P. Beame, M. Saks, X. Sun, E. Vee, Electronic Colloquium in Computational Complexity:TR00-025, 2000 .
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. Tompa, SIAM Journal on Computing 28:3, 1999 : 1051–1072.
Time-Space Tradeoffs for Branching Programs
P. Beame, M. Saks, J.S. Thathachar, Proceedings 39th Annual Symposium on Foundations of Computer Science, IEEE, 1998 : 254-263.
Time-Space Tradeoffs for Branching Programs
P. Beame, M. Saks, J.S. Thathachar, Electronic 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. Tompa, Information and Computation 130:2, 1996 : 101-129.
Communication-Space Tradeoffs for Unrestricted Protocols
P. Beame, M. Tompa, P. Yan, SIAM 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. Tompa, Department 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. Beame, SIAM 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. Tompa, Proceedings 31st Annual Symposium on Foundations of Computer Science, IEEE, 1990 : 429-438.
Communication-Space Tradeoffs for Unrestricted Protocols
P. Beame, M. Tompa, P. Yan, Proceedings 31st Annual Symposium on Foundations of Computer Science, IEEE, 1990 : 420-428.
Communication-Space Tradeoffs for Unrestricted Protocols
P. Beame, M. Tompa, P. Yan, Department of Computer Science and Engineering, University of Washington:UW-CSE-90-01-12, 1990 .
A General Sequential Time-Space Tradeoff for Finding Unique Elements
P. Beame, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, 1989 : 197-203.
A General Sequential Time-Space Tradeoff for Finding Unique Elements
P. Beame, Department of Computer Science and Engineering, University of Washington:UW-CSE-88-10-04, 1988 .
Communication Complexity and Data Streams
On Disperser/Lifting Properties of the Index and Inner-Product Functions
P. Beame, S. Koroth, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10–13, 2023, Cambridge, MA, USA, Schloss Dagstuhl – Leibniz-Zentrum für Informatik 251, 2023 : 14:1-14:17.
On Disperser/Lifting Properties of the Index and Inner-Product Functions
P. Beame, S. Koroth, CoRR abs/2211.17211, 2022 .
http://arxiv.org/abs/2211.17211 Arxiv http://eccc.weizmann.ac.il/report/2022/173/index.html ECCC Technical Report TR22-173
Communication Steps for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, Journal 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. Rashtchian, Proceedings of the Twenty-Eighth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2017 : 289–306.
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
P. Beame, C. Rashtchian, CoRR abs/1611.04999, 2016 .
Worst-Case Optimal Algorithms for Parallel Query Processing
P. Koutris, P. Beame, D. Suciu, Proceedings of 19th International Conference on Database Theory, 2016 : 8:1–8:18.
Communication Cost in Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1602.06236, 2016 .
Worst-Case Optimal Algorithms for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1604.01848, 2016 .
Skew in Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, Proceedings of the Thirty-Third Annual ACM Symposium on Principles of Database Systems, 2014 : 212–223.
Skew in Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1401.1872, 2014 .
Communication Steps for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, Proceedings of the Thirty-Second Annual ACM Symposium on Principles of Database Systems, 2013 : 273–284. Winner of 2023 ACM PODS Alberto O. Mendelzon Test-of-Time Award.
Communication Steps for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1306.5972, 2013 .
Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$
P. Beame, T. Huynh, SIAM Journal on Computing 41:3, 2012 : 484–518.
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments
P. Beame, T. Huynh, ACM Transactions on Computation Theory 3:2, 2011 : 6.1–6.22.
Hardness Amplification in Proof Complexity
P. Beame, T. Huynh, T. Pitassi, Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, 2010 : 87–96.
Separating Deterministic from Randomized Multiparty Communication Complexity
P. Beame, M. David, T. Pitassi, P. Woelfel, Theory of Computing 6, 2010 : 201–225.
Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$
P. Beame, D.T. Huynh-Ngoc, Proceedings 50th Annual Symposium on Foundations of Computer Science, IEEE, 2009 : 53–62.
Hardness Amplification in Proof Complexity
P. Beame, T. Huynh, T. Pitassi, Electronic Colloquium in Computational Complexity:TR09-072, 2009 .
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments
P. Beame, D.T. Huynh-Ngoc, Proceedings 49th Annual Symposium on Foundations of Computer Science, IEEE, 2008 : 499–508.
Multiparty Communication Complexity and Threshold Circuit Complexity of $AC^0$
P. Beame, D.T. Huynh-Ngoc, Electronic Colloquium in Computational Complexity:TR08-082, 2008 .
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments
P. Beame, D.T. Huynh-Ngoc, Electronic Colloquium in Computational Complexity:TR08-024, 2008 .
Lower Bounds for Randomized Read/Write Stream Algorithms
P. Beame, T.S. Jayram, A. Rudra, Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007 : 689–698.
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
P. Beame, M. David, T. Pitassi, P. Woelfel, Automata, Languages, and Programming: 34th International Colloquium (ICALP 2007), 2007 : 134–145.
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
P. Beame, T. Pitassi, N. Segerlind, SIAM Journal on Computing 37:3, 2007 : 845–869.
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Set Disjointness
P. Beame, T. Pitassi, N. Segerlind, A. Wigderson, Computational Complexity 15:4, 2006 : 391–432. Invited submission for special issue on CCC 2005.
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
P. Beame, T. Pitassi, N. Segerlind, Electronic Colloquium in Computational Complexity:TR05-053, 2005 .
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
P. Beame, T. Pitassi, N. Segerlind, Automata, Languages, and Programming: 32nd International Colloquium (ICALP 2005), 2005 : 1176–1188.
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
P. Beame, T. Pitassi, N. Segerlind, A. Wigderson, Proceedings Twentieth Annual IEEE Conference on Computational Complexity, 2005 : 52–66.
Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems
P. Beame, E. Vee, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002 : 688-697.
Communication-Space Tradeoffs for Unrestricted Protocols
P. Beame, M. Tompa, P. Yan, SIAM Journal on Computing 23:3, 1994 : 652-661.
Randomized versus Nondeterministic Communication Complexity
P. Beame, J. Lawry, Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992 : 188-199.
Verification of Software and Hardware
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning
V. Liew, P. Beame, J. Devriendt, J. Elfers, J. Nordström, Proceedings of the 20th Conference on Formal Methods in Computer Aided Design – FMCAD 2020, TU Wein Academic Press, 2020 : 194–204.
Toward Verifying Nonlinear Integer Arithmetic
P. Beame, V. Liew, Journal of the ACM 66:3, 2019 : 22:1-30.
Towards Verifying Nonlinear Integer Arithmetic
P. Beame, V. Liew, Computer Aided Verification, 29th International Conference, CAV’17 Proceedings, Part II, 2017 : 238–258.
Towards Verifying Nonlinear Integer Arithmetic
P. Beame, V. Liew, CoRR abs/1705.04302, 2017 .
Optimizing Symbolic Model-Checking for Statecharts
W. Chan, R.J. Anderson, P. Beame, D.J. Jones, D. Notkin, W.E. Warner, IEEE Transactions on Software Engineering 27:2, 2001 : 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. Warner, Proceedings 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. Notkin, Proceedings 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. Reese, IEEE 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. Notkin, ISSTA 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
Combining Constraint Solving and Symbolic Model Checking for a Class of Systems with Non-Linear Constraints
W. Chan, R.J. Anderson, P. Beame, D. Notkin, Computer Aided Verification, 9th International Conference, CAV’97 Proceedings, Springer-Verlag 1254, 1997 : 316–327.
Model Checking Large Software Specifications
R.J. Anderson, P. Beame, S. Burns, W. Chan, F. Modugno, D. Notkin, J.D. Reese, Proceedings of the 4th ACM SIGSOFT Symposium on the Foundations of Software Engineering, 1996 : 156–166. Also published as \textitSoftware Engineering Notes, 21(6), November 1996
Proof Complexity and Satisfiability
On Disperser/Lifting Properties of the Index and Inner-Product Functions
P. Beame, S. Koroth, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10–13, 2023, Cambridge, MA, USA, Schloss Dagstuhl – Leibniz-Zentrum für Informatik 251, 2023 : 14:1-14:17.
On Disperser/Lifting Properties of the Index and Inner-Product Functions
P. Beame, S. Koroth, CoRR abs/2211.17211, 2022 .
http://arxiv.org/abs/2211.17211 Arxiv http://eccc.weizmann.ac.il/report/2022/173/index.html ECCC Technical Report TR22-173
Adding Dual Variables to Algebraic Reasoning for Circuit Verification
D. Kaufmann, P. Beame, A. Biere, J. Nordström, Proceedings of 25th Design, Automation and Test in Europe (DATE), IEEE, 2022 : 1435–1440.
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning
V. Liew, P. Beame, J. Devriendt, J. Elfers, J. Nordström, Proceedings of the 20th Conference on Formal Methods in Computer Aided Design – FMCAD 2020, TU Wein Academic Press, 2020 : 194–204.
Toward Verifying Nonlinear Integer Arithmetic
P. Beame, V. Liew, Journal of the ACM 66:3, 2019 : 22:1-30.
Smoothing Structured Decomposable Circuits
A. Shih, G. Van den Broeck, P. Beame, A. Amarilli, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 2019 : 11412–11422.
Smoothing Structured Decomposable Circuits
A. Shih, G. Van den Broeck, P. Beame, A. Amarilli, CoRR abs/1906.00311, 2019 .
Stabbing Planes
P. Beame, N. Fleming, R. Impagliazzo, A. Kolokolova, D. Pankratov, T. Pitassi, R. Robere, Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 94, 2018 : 10:1–10:20.
Towards Verifying Nonlinear Integer Arithmetic
P. Beame, V. Liew, Computer Aided Verification, 29th International Conference, CAV’17 Proceedings, Part II, 2017 : 238–258.
Towards Verifying Nonlinear Integer Arithmetic
P. Beame, V. Liew, CoRR abs/1705.04302, 2017 .
Exact Model Counting of Query Expressions: Limitations of Propositional Methods
P. Beame, J. Li, S. Roy, D. Suciu, ACM Transactions on Database Systems 42:1, 2017 : 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. Robere, CoRR abs/1710.03219, 2017 . Also Technical Report TR17-151 # eccc # available at http://eccc.uni-trier.de/eccc-reports/2017/151/index.html
http://arxiv.org/abs/1710.03219 Arxiv http://eccc.uni-trier.de/eccc-reports/2017/151/index.html ECCC Technical Report TR17-151
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
P. Beame, C. Beck, R. Impagliazzo, SIAM Journal on Computing 45:4, 2016 : 1612–1645.
New Limits for Knowledge Compilation and Applications to Exact Model Counting
P. Beame, V. Liew, Proceedings 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. Suciu, Proceedings 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. Liew, CoRR abs/1506.02639, 2015 .
Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution
P. Beame, A. Sabharwal, Proceedings, AAAI-14: Twenty-Eighth National Conference on Artificial Intelligence, American Association for Artificial Intelligence, 2014 : 2608–2615.
Model Counting of Query Expressions: Limitations of Propositional Methods
P. Beame, J. Li, S. Roy, D. Suciu, Proceedings of 17th International Conference on Database Theory, 2014 : 177–188.
Symmetric Weighted First-Order Model Counting
P. Beame, G. Van den Broeck, E. Gribkoff, D. Suciu, CoRR abs/1506.02639, 2014 .
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
P. Beame, J. Li, S. Roy, D. Suciu, Proceedings 29th Conference on Uncertainty in Artificial Intelligence, 2013 : 52–61.
Model Counting of Query Expressions: Limitations of Propositional Methods
P. Beame, J. Li, S. Roy, D. Suciu, CoRR abs/1312.4125, 2013 .
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
P. Beame, C. Beck, R. Impagliazzo, Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012 : 212–232.
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
P. Beame, C. Beck, R. Impagliazzo, Electronic Colloquium in Computational Complexity:TR11-149, 2011 .
Hardness Amplification in Proof Complexity
P. Beame, T. Huynh, T. Pitassi, Proceedings 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. Segerlind, ACM Transactions on Computation Theory 1:3, 2010 : 9:1-33.
Hardness Amplification in Proof Complexity
P. Beame, T. Huynh, T. Pitassi, Electronic Colloquium in Computational Complexity:TR09-072, 2009 .
A dynamic approach for MPE and Weighted MAX-SAT
T. Sang, P. Beame, H. Kautz, Proceedings of the 20th International Joint Conference in Artificial Intelligence (IJCAI), 2007 : 173–179.
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs
P. Beame, R. Impagliazzo, A. Sabharwal, Computational 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. Segerlind, SIAM Journal on Computing 37:3, 2007 : 845–869.
Formula Caching in DPLL
P. Beame, R. Impagliazzo, T. Pitassi, N. Segerlind, Electronic Colloquium in Computational Complexity:TR06-140, 2006 .
Performing Bayesian Inference by Weighted Model Counting.
T. Sang, P. Beame, H. Kautz, Proceedings, AAAI-05: Twentieth National Conference on Artificial Intelligence, American Association for Artificial Intelligence, 2005 : 475-482.
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
P. Beame, T. Pitassi, N. Segerlind, Automata, Languages, and Programming: 32nd International Colloquium (ICALP 2005), 2005 : 1176–1188.
The Resolution Complexity of Random Graph $k$-Colorability
P. Beame, J. Culberson, D. Mitchell, C. Moore, Discrete Applied Mathematics 153, 2005 : 25–47.
Heuristics for fast exact model counting
T. Sang, P. Beame, H. Kautz, SAT, Springer 3569, 2005 : 226–240.
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
P. Beame, T. Pitassi, N. Segerlind, Electronic Colloquium in Computational Complexity:TR05-053, 2005 .
A sharp threshold in proof complexity yields lower bounds for satisfiability search
D. Achlioptas, P. Beame, M. Molloy, Journal of Computer and System Sciences 68:2, 2004 : 238–268. Special issue of invited papers from STOC 2001 conference
Exponential Bounds for DPLL Below the Satisfiability Threshold
D. Achlioptas, P. Beame, M. Molloy, Proceedings of the Fifteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2004 : 139–140.
Bounded-depth Frege lower bounds for weaker pigeonhole principles
J. Buresh-Oppenheim, P. Beame, T. Pitassi, R. Raz, A. Sabharwal, SIAM Journal on Computing 34:2, 2004 : 261–276.
A sharp threshold in proof complexity yields lower bounds for satisfiability search
D. Achlioptas, P. Beame, M. Molloy, Journal of Computer and System Sciences 68:2, 2004 : 238–268.
Towards understanding and harnessing the potential of clause learning
P. Beame, H. Kautz, A. Sabharwal, Journal of Artificial Intelligence Research 22, 2004 : 319–351. Honorable mention (sole runner up) 2008 IJCAI-JAIR Best Paper Prize
Combining Component Caching and Clause Learning for Effective Model Counting
T. Sang, F. Bacchus, P. Beame, H. Kautz, T. Pitassi, SAT 2004, Satisfiability Conference, 2004 : 20–28.
Proof Complexity
P. Beame, Computational Complexity Theory, American Mathematical Society 10, 2004 : 199–246.
The Resolution Complexity of Random Graph $k$-Colorability
P. Beame, J. Culberson, D. Mitchell, C. Moore, Electronic Colloquium in Computational Complexity:TR04-012, 2004 .
On the power of clause learning
P. Beame, H. Kautz, A. Sabharwal, Proceedings of the 18th International Joint Conference in Artificial Intelligence (IJCAI), 2003 : 94–99.
Memoization and DPLL: Formula Caching Proof Systems
P. Beame, R. Impagliazzo, T. Pitassi, N. Segerlind, Proceedings Eighteenth Annual IEEE Conference on Computational Complexity, 2003 : 225–236.
Using Problem Structure for Efficient Clause Learning
A. Sabharwal, P. Beame, H. Kautz, Proceedings of the Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT 2003), 2003 : 159–166.
Bounded-depth Frege lower bounds for weaker pigeonhole principles
J. Buresh-Oppenheim, P. Beame, T. Pitassi, R. Raz, A. Sabharwal, Proceedings 43rd Annual Symposium on Foundations of Computer Science, IEEE, 2002 : 583–592.
The efficiency of resolution and Davis-Putnam procedures
P. Beame, R. Karp, T. Pitassi, M. Saks, SIAM Journal on Computing 31:4, 2002 : 1048–1075.
Bounded-depth Frege lower bounds for weaker pigeonhole principles
J. Buresh-Oppenheim, P. Beame, T. Pitassi, R. Raz, A. Sabharwal, Electronic Colloquium in Computational Complexity:TR02-023, 2002 .
A sharp threshold in proof complexity
D. Achlioptas, P. Beame, M. Molloy, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, 2001 : 337–346.
The Resolution Complexity of the Independent Set Problem in Random Graphs
P. Beame, R. Impagliazzo, A. Sabharwal, Proceedings Sixteenth Annual IEEE Conference on Computational Complexity, 2001 : 52-68.
Propositional Proof Complexity: Past, Present, and Future
P. Beame, T. Pitassi, Current Trends in Theoretical Computer Science: Entering the 21st Century, World Scientific Publishing, 2001 : 42–70.
Propositional Proof Complexity: Past, Present, and Future
P. Beame, T. Pitassi, Bulletin of the European Association for Theoretical Computer Science 65, 1998 . The Computational Complexity Column (ed. E. Allender).
On the complexity of unsatisfiability of random $k$-CNF formulas
P. Beame, R. Karp, T. Pitassi, M. Saks, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998 : 561-571.
The Relative Complexity of NP Search Problems
P. Beame, S.A. Cook, J. Edmonds, R. Impagliazzo, T. Pitassi, Journal of Computer and System Sciences 57, 1998 : 3–19. Special issue of invited papers from 1995 STOC conference.
Proof Complexity and Feasible Arithmetics
, Proof Complexity and Feasible Arithmetics, American Mathematical Society 39, 1998 .
More on the Relative Strength of Counting Principles
P. Beame, S. Riis, Proof Complexity and Feasible Arithmetics, American Mathematical Society 39, 1998 : 13-35.
Simplified and Improved Resolution Lower Bounds
P. Beame, T. Pitassi, Proceedings 37th Annual Symposium on Foundations of Computer Science, IEEE, 1996 : 274–282.
An Exponential Separation between the Parity Principle and the Pigeonhole Principle
P. Beame, T. Pitassi, Annals 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ák, Proc. 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. Pitassi, Proceedings 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íček, T. Pitassi, P. Pudlák, Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994 : 794-806.
An Exponential Separation between the Matching Principle and the Pigeonhole Principle
P. Beame, T. Pitassi, 8th Annual IEEE Symposium on Logic in Computer Science, 1993 : 308–319.
An Exponential Separation between the Matching Principle and the Pigeonhole Principle
P. Beame, T. Pitassi, Department of Computer Science and Engineering, University of Washington:UW-CSE-93-04-07, 1993 .
Exponential Lower Bounds for the Pigeonhole Principle
T. Pitassi, P. Beame, R. Impagliazzo, Computational Complexity 3:2, 1993 : 97–140.
Exponential Lower Bounds for the Pigeonhole Principle
P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi, P. Pudlák, A. Woods, Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992 : 200-220.
Exponential Lower Bounds for the Pigeonhole Principle
P. Beame, R. Impagliazzo, T. Pitassi, University of Toronto, Department of Computer Science:TR257/91, 1991 .
Parallel and Distributed Computing
Towards a Complexity Theory of Parallel Computation
P. Beame, P. McKenzie, Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook, Association for Computing Machinery, 2023 : 107–126.
Communication Steps for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, Journal 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. Rashtchian, Proceedings of the Twenty-Eighth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2017 : 289–306.
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
P. Beame, C. Rashtchian, CoRR abs/1611.04999, 2016 .
Nondeterminism and an abstract formulation of Nečiporuk’s lower bound method
P. Beame, N. Grosshans, P. McKenzie, L. Segoufin, CoRR abs/1608.01932, 2016 .
Worst-Case Optimal Algorithms for Parallel Query Processing
P. Koutris, P. Beame, D. Suciu, Proceedings of 19th International Conference on Database Theory, 2016 : 8:1–8:18.
Communication Cost in Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1602.06236, 2016 .
Worst-Case Optimal Algorithms for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1604.01848, 2016 .
Skew in Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, Proceedings of the Thirty-Third Annual ACM Symposium on Principles of Database Systems, 2014 : 212–223.
Skew in Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1401.1872, 2014 .
Communication Steps for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, Proceedings of the Thirty-Second Annual ACM Symposium on Principles of Database Systems, 2013 : 273–284. Winner of 2023 ACM PODS Alberto O. Mendelzon Test-of-Time Award.
Communication Steps for Parallel Query Processing
P. Beame, P. Koutris, D. Suciu, CoRR abs/1306.5972, 2013 .
Parallel Algorithms for Arrangements
R.J. Anderson, P. Beame, E. Brisson, Algorithmica 15:2, 1996 : 104-125. Special issue of invited papers from 1990 SPAA conference
http://www.cs.washington.edu/homes/beame/papers/arrangejournal.pdf preprint http://link.springer.com/article/10.1007%2FBF01941684 journal link
Information Broadcasting by Exclusive Read PRAMs
P. Beame, M. Kik, M. Kutyłowski, Parallel Processing Letters 4:1&2, 1994 : 159-169.
http://www.cs.washington.edu/homes/beame/papers/broadcast.ps preprint http://www.worldscientific.com/doi/abs/10.1142/S012962649400017X journal link
The Complexity of Computing Symmetric Functions using Threshold Circuits
P. Beame, E. Brisson, R.E. Ladner, Theoretical Computer Science 100, 1992 : 253-265.
Parallel Algorithms for Arrangements
R.J. Anderson, P. Beame, E. Brisson, Proceedings 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. Ruzzo, Proceedings 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. Ruzzo, Department of Computer Science and Engineering, University of Washington:UW-CSE-90-04-03, 1990 .
The Complexity of Computing Symmetric Functions using Threshold Circuits
P. Beame, E. Brisson, R.E. Ladner, Department of Computer Science and Engineering, University of Washington:UW-CSE-90-01-01, 1990 .
Parallel Search for Maximal Independence Given Minimal Dependence
P. Beame, M. Luby, Proceedings of the First Annual {ACM-SIAM} Symposium on Discrete Algorithms, ACM, 1990 : 212-218.
Lower Bounds for Recognizing Small Cliques on CRCW PRAM’s
P. Beame, Discrete 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. Brisson, Department of Computer Science and Engineering, University of Washington:UW-CSE-89-12-08, 1989 .
Distributed Computing on Transitive Networks: The Torus
P. Beame, H. Bodlaender, {STACS} 89: 6th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag 349, 1989 : 294-303.
http://www.cs.washington.edu/homes/beame/papers/grid.ps preprint http://link.springer.com/chapter/10.1007%2FBFb0028993 conference proceedings link
Parallel Search for Maximal Independence Given Minimal Dependence
P. Beame, M. Luby, International Computer Science Institute:TR-89-003, 1989 .
Limits on the Power of Concurrent-Write Parallel Machines
P. Beame, Information and Computation 76:1, 1988 : 13-28.
Distributed Computing on Transitive Networks: The Torus
P. Beame, H. Bodlaender, Department 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. Hoover, SIAM Journal on Computing 15:4, 1986 : 994-1003.
Lower Bounds in Parallel Machine Computation
P.W. Beame, University of Toronto, 1986 . Department of Computer Science Technical Report 198/87
Log Depth Circuits for Division and Related Problems
P.W. Beame, S.A. Cook, J.H. Hoover, 25th Annual Symposium on Foundations of Computer Science, IEEE, 1984 : 1-6.
Random Routing in Constant Degree Networks
P.W. Beame, Department of Computer Science, 1982 . Technical Report 161/82
Data Structures
Optimal Bounds for the Predecessor Problem and Related Problems
P. Beame, F. Fich, Journal 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. Vee, Proceedings 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. Fich, Journal of Computer and System Sciences 65:1, 2002 : 38–72.
Optimal Bounds for the Predecessor Problem
P. Beame, F. Fich, Proceedings 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. Fich, Department 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. Segoufin, CoRR abs/1608.01932, 2016 .
Nondeterminism and an Abstract Formulation of Nečiporuk’s Lower Bound Method
P. Beame, N. Grosshans, P. McKenzie, L. Segoufin, ACM Transactions on Computation Theory 9:1, 2016 : 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. Srinivasan, Proceedings Twenty-Seventh Annual IEEE Conference on Computational Complexity, 2012 : 117–125.
The Quantum Query Complexity of $AC^0$
P. Beame, W. Machmouchi, Quantum Information \& Computation 12:7–8, 2012 : 670–676.
Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$
P. Beame, T. Huynh, SIAM Journal on Computing 41:3, 2012 : 484–518.
A Note on Neciporuk’s Method for Nondeterministic Branching Programs
P. Beame, P. McKenzie, 2011 .
The Quantum Query Complexity of $AC^0$
P. Beame, W. Machmouchi, arxiv/quant-phys:arXiv:1008.2422v1, 2010 .
Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$
P. Beame, D.T. Huynh-Ngoc, Proceedings 50th Annual Symposium on Foundations of Computer Science, IEEE, 2009 : 53–62.
Multiparty Communication Complexity and Threshold Circuit Complexity of $AC^0$
P. Beame, D.T. Huynh-Ngoc, Electronic Colloquium in Computational Complexity:TR08-082, 2008 .
Improved Depth Bounds for Small Distance Connectivity
P. Beame, R. Impagliazzo, T. Pitassi, Computational Complexity 7:4, 1998 : 325–345.
Separating the Power of EREW and CREW PRAMs with Small Communication Width
P. Beame, F.E. Fich, R. Sinha, Information and Computation 138:1, 1997 : 89-99.
Improved Depth Bounds for Small Distance Connectivity
P. Beame, R. Impagliazzo, T. Pitassi, Proceedings 36th Annual Symposium on Foundations of Computer Science, IEEE, 1995 : 692-701.
A Switching Lemma Primer
P. Beame, Department 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. Sinha, Proceedings of the 1993 Workshop on Algorithms and Data Structures, 1993 : 163-174.
http://www.cs.washington.edu/homes/beame/papers/crew.ps preprint http://link.springer.com/chapter/10.1007%2F3-540-57155-8_245 conference proceedings
The Complexity of Computing Symmetric Functions using Threshold Circuits
P. Beame, E. Brisson, R.E. Ladner, Theoretical Computer Science 100, 1992 : 253-265.
Lower Bounds for Recognizing Small Cliques on CRCW PRAM’s
P. Beame, Discrete 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åstad, Journal of the ACM 36:3, 1989 : 643-670.
Limits on the Power of Concurrent-Write Parallel Machines
P. Beame, Information and Computation 76:1, 1988 : 13-28.
Optimal Bounds for Decision Problems on the CRCW PRAM
P. Beame, J. Håstad, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987 : 83-93.
Lower Bounds for Recognizing Small Cliques on CRCW PRAM’s
P. Beame, Laboratory for Computer Science, M.I.T.:TM–336, 1987 .
Limits on the Power of Concurrent-Write Parallel Machines
P. Beame, Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 1986 : 169-176.
Lower Bounds in Parallel Machine Computation
P.W. Beame, University of Toronto, 1986 . Department of Computer Science Technical Report 198/87
Other topics
Edge Estimation with Independent Set Oracles
P. Beame, S. Har-Peled, S.Natarajan Ramamoorthy, C. Rashtchian, M. Sinha, ACM Transactions on Algorithms 16:4, 2020 : 52:1-52:27.
On the Bias of Reed-Muller Codes over Odd Prime Fields
P. Beame, S.Oveis Gharan, X. Yang, SIAM Journal on Discrete Mathematics 34:2, 2020 : 1232–1247.
Edge Estimation with Independent Set Oracles
P. Beame, S. Har-Peled, S.Natarajan Ramamoorthy, C. Rashtchian, M. Sinha, Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 94, 2018 : 38:1–38:21.
On the Bias of Reed-Muller Codes over Odd Prime Fields
P. Beame, S.Oveis Gharan, X. Yang, CoRR abs/1806.06973, 2018 .
The Quantum Query Complexity of $AC^0$
P. Beame, W. Machmouchi, Quantum Information \& Computation 12:7–8, 2012 : 670–676.
The Quantum Query Complexity of $AC^0$
P. Beame, W. Machmouchi, arxiv/quant-phys:arXiv:1008.2422v1, 2010 .
Longest Common Subsequences in Sets of Permutations
P. Beame, E. Blais, D.T. Huynh-Ngoc, arxiv/math.co:arXiv:0904.1615, 2009 .
The Relative Complexity of NP Search Problems
P. Beame, S.A. Cook, J. Edmonds, R. Impagliazzo, T. Pitassi, Journal of Computer and System Sciences 57, 1998 : 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. Pitassi, Proceedings 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. Muir, BIT 29, 1989 : 126-139.