


default search action
Paul Beame
Person information
- affiliation: University of Washington, Seattle, Washington, USA
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c72]Paul Beame
, Niels Kornerup
, Michael Whitmeyer
:
Quantum Time-Space Tradeoffs for Matrix Problems. STOC 2024: 596-607 - [i48]Paul Beame, Niels Kornerup
:
Quantum Time-Space Tradeoffs for Matrix Problems. CoRR abs/2401.05321 (2024) - [i47]Paul Beame, Michael Whitmeyer:
Multiparty Communication Complexity of Collision Finding. CoRR abs/2411.07400 (2024) - [i46]Paul Beame, Niels Kornerup:
Quantum Time-Space Tradeoffs for Matrix Problems. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c71]Paul Beame, Niels Kornerup:
Cumulative Memory Lower Bounds for Randomized and Quantum Computation. ICALP 2023: 17:1-17:20 - [c70]Paul Beame
, Sajin Koroth:
On Disperser/Lifting Properties of the Index and Inner-Product Functions. ITCS 2023: 14:1-14:17 - [p3]Paul Beame
, Pierre McKenzie:
Towards a Complexity Theory of Parallel Computation. Logic, Automata, and Computational Complexity 2023: 107-126 - [i45]Paul Beame, Niels Kornerup
:
Cumulative Memory Lower Bounds for Randomized and Quantum Computation. CoRR abs/2301.05680 (2023) - [i44]Paul Beame, Niels Kornerup:
Cumulative Memory Lower Bounds for Randomized and Quantum Computation. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [c69]Daniela Kaufmann
, Paul Beame
, Armin Biere, Jakob Nordström
:
Adding Dual Variables to Algebraic Reasoning for Gate-Level Multiplier Verification. DATE 2022: 1431-1436 - [i43]Paul Beame, Sajin Koroth:
On Disperser/Lifting Properties of the Index and Inner-Product Functions. CoRR abs/2211.17211 (2022) - [i42]Paul Beame, Sajin Koroth:
On Disperser/Lifting Properties of the Index and Inner-Product Functions. Electron. Colloquium Comput. Complex. TR22 (2022) - 2020
- [j44]Paul Beame
:
Technical perspective: Two for the price of one. Commun. ACM 63(10): 96 (2020) - [j43]Paul Beame
, Shayan Oveis Gharan, Xin Yang:
On the Bias of Reed-Muller Codes over Odd Prime Fields. SIAM J. Discret. Math. 34(2): 1232-1247 (2020) - [j42]Paul Beame
, Sariel Har-Peled
, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian
, Makrand Sinha:
Edge Estimation with Independent Set Oracles. ACM Trans. Algorithms 16(4): 52:1-52:27 (2020) - [c68]Vincent Liew, Paul Beame
, Jo Devriendt, Jan Elffers, Jakob Nordström
:
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning. FMCAD 2020: 194-204
2010 – 2019
- 2019
- [j41]Paul Beame
, Vincent Liew:
Toward Verifying Nonlinear Integer Arithmetic. J. ACM 66(3): 22:1-22:30 (2019) - [c67]Andy Shih, Guy Van den Broeck, Paul Beame, Antoine Amarilli:
Smoothing Structured Decomposable Circuits. NeurIPS 2019: 11412-11422 - [i41]Andy Shih, Guy Van den Broeck, Paul Beame, Antoine Amarilli:
Smoothing Structured Decomposable Circuits. CoRR abs/1906.00311 (2019) - 2018
- [c66]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. COLT 2018: 843-856 - [c65]Paul Beame
, Noah Fleming, Russell Impagliazzo
, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. ITCS 2018: 10:1-10:20 - [c64]Paul Beame
, Sariel Har-Peled
, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha:
Edge Estimation with Independent Set Oracles. ITCS 2018: 38:1-38:21 - [i40]Paul Beame, Shayan Oveis Gharan, Xin Yang:
On the Bias of Reed-Muller Codes over Odd Prime Fields. CoRR abs/1806.06973 (2018) - [i39]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j40]Paul Beame
, Paraschos Koutris, Dan Suciu
:
Communication Steps for Parallel Query Processing. J. ACM 64(6): 40:1-40:58 (2017) - [j39]Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
:
Exact Model Counting of Query Expressions: Limitations of Propositional Methods. ACM Trans. Database Syst. 42(1): 1:1-1:46 (2017) - [c63]Paul Beame, Vincent Liew:
Towards Verifying Nonlinear Integer Arithmetic. CAV (2) 2017: 238-258 - [c62]Paul Beame
, Cyrus Rashtchian:
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube. SODA 2017: 289-306 - [i38]Paul Beame, Vincent Liew:
Towards Verifying Nonlinear Integer Arithmetic. CoRR abs/1705.04302 (2017) - [i37]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. CoRR abs/1708.02640 (2017) - [i36]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. CoRR abs/1710.03219 (2017) - [i35]Paul Beame, Sariel Har-Peled
, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha:
Edge Estimation with Independent Set Oracles. CoRR abs/1711.07567 (2017) - [i34]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. Electron. Colloquium Comput. Complex. TR17 (2017) - [i33]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j38]Paul Beame, Chris Beck
, Russell Impagliazzo
:
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. SIAM J. Comput. 45(4): 1612-1645 (2016) - [j37]Paul Beame, Nathan Grosshans
, Pierre McKenzie, Luc Segoufin:
Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method. ACM Trans. Comput. Theory 9(1): 5:1-5:34 (2016) - [c61]Paraschos Koutris, Paul Beame, Dan Suciu
:
Worst-Case Optimal Algorithms for Parallel Query Processing. ICDT 2016: 8:1-8:18 - [i32]Paul Beame, Paraschos Koutris, Dan Suciu:
Communication Cost in Parallel Query Processing. CoRR abs/1602.06236 (2016) - [i31]Paul Beame, Paraschos Koutris, Dan Suciu:
Worst-Case Optimal Algorithms for Parallel Query Processing. CoRR abs/1604.01848 (2016) - [i30]Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin:
Nondeterminism and an abstract formulation of Nečiporuk's lower bound method. CoRR abs/1608.01932 (2016) - [i29]Paul Beame, Cyrus Rashtchian:
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube. CoRR abs/1611.04999 (2016) - 2015
- [c60]Paul Beame, Vincent Liew, Mihai Patrascu:
Finding the Median (Obliviously) with Bounded Space. ICALP (1) 2015: 103-115 - [c59]Paul Beame
, Guy Van den Broeck, Eric Gribkoff, Dan Suciu
:
Symmetric Weighted First-Order Model Counting. PODS 2015: 313-328 - [c58]Paul Beame, Vincent Liew:
New Limits for Knowledge Compilation and Applications to Exact Model Counting. UAI 2015: 131-140 - [i28]Paul Beame, Vincent Liew, Mihai Patrascu:
Finding the Median (Obliviously) with Bounded Space. CoRR abs/1505.00090 (2015) - [i27]Paul Beame, Vincent Liew:
New Limits for Knowledge Compilation and Applications to Exact Model Counting. CoRR abs/1506.02639 (2015) - 2014
- [c57]Paul Beame
, Ashish Sabharwal:
Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution. AAAI 2014: 2608-2615 - [c56]Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu:
Counting of Query Expressions: Limitations of Propositional Methods. ICDT 2014: 177-188 - [c55]Paul Beame
, Paraschos Koutris, Dan Suciu
:
Skew in parallel query processing. PODS 2014: 212-223 - [i26]Paul Beame, Paraschos Koutris, Dan Suciu:
Skew in Parallel Query Processing. CoRR abs/1401.1872 (2014) - [i25]Paul Beame, Guy Van den Broeck, Eric Gribkoff, Dan Suciu:
Symmetric Weighted First-Order Model Counting. CoRR abs/1412.1505 (2014) - 2013
- [c54]Paul Beame
, Raphaël Clifford, Widad Machmouchi:
Element Distinctness, Frequency Moments, and Sliding Windows. FOCS 2013: 290-299 - [c53]Paul Beame
, Paraschos Koutris, Dan Suciu
:
Communication steps for parallel query processing. PODS 2013: 273-284 - [c52]Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu:
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases. UAI 2013 - [i24]Paul Beame, Paraschos Koutris, Dan Suciu:
Communication Steps for Parallel Query Processing. CoRR abs/1306.5972 (2013) - [i23]Paul Beame, Raphaël Clifford, Widad Machmouchi:
Element Distinctness, Frequency Moments, and Sliding Windows. CoRR abs/1309.3690 (2013) - [i22]Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu:
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases. CoRR abs/1309.6815 (2013) - [i21]Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu:
Model Counting of Query Expressions: Limitations of Propositional Methods. CoRR abs/1312.4125 (2013) - [i20]Paul Beame, Raphaël Clifford, Widad Machmouchi:
Element Distinctness, Frequency Moments, and Sliding Windows. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j36]Paul Beame
, Widad Machmouchi:
The quantum query complexity of AC0. Quantum Inf. Comput. 12(7-8): 670-676 (2012) - [j35]Paul Beame
, Trinh Huynh:
Multiparty Communication Complexity and Threshold Circuit Size of sfAC0. SIAM J. Comput. 41(3): 484-518 (2012) - [j34]Paul Beame, Trinh Huynh:
The Value of Multiple Read/Write Streams for Approximating Frequency Moments. ACM Trans. Comput. Theory 3(2): 6:1-6:22 (2012) - [c51]Paul Beame
, Russell Impagliazzo
, Srikanth Srinivasan
:
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. CCC 2012: 117-125 - [c50]Paul Beame
, Christopher Beck
, Russell Impagliazzo
:
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC 2012: 213-232 - [i19]Paul Beame, Raphaël Clifford, Widad Machmouchi:
Sliding Windows with Limited Storage. CoRR abs/1212.4372 (2012) - [i18]Paul Beame, Raphaël Clifford, Widad Machmouchi:
Sliding Windows With Limited Storage. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c49]Paul Beame
, Widad Machmouchi:
Making Branching Programs Oblivious Requires Superlogarithmic Overhead. CCC 2011: 12-22 - [i17]Paul Beame, Henry A. Kautz, Ashish Sabharwal:
Towards Understanding and Harnessing the Potential of Clause Learning. CoRR abs/1107.0044 (2011) - [i16]Paul Beame, Chris Beck, Russell Impagliazzo:
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j33]Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel:
Separating Deterministic from Randomized Multiparty Communication Complexity. Theory Comput. 6(1): 201-225 (2010) - [j32]Paul Beame
, Russell Impagliazzo
, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL. ACM Trans. Comput. Theory 1(3): 9:1-9:33 (2010) - [c48]Paul Beame, Trinh Huynh, Toniann Pitassi:
Hardness amplification in proof complexity. STOC 2010: 87-96 - [i15]Paul Beame, Widad Machmouchi:
The Quantum Query Complexity of AC0. CoRR abs/1008.2422 (2010) - [i14]Paul Beame, Widad Machmouchi:
Making RAMs Oblivious Requires Superlogarithmic Overhead. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j31]Paul Beame
, Amit Chakrabarti
:
Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. Comput. Complex. 18(2): 169-170 (2009) - [c47]Paul Beame
, Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity and Threshold Circuit Size of AC^0. FOCS 2009: 53-62 - [i13]Paul Beame, Trinh Huynh, Toniann Pitassi:
Hardness Amplification in Proof Complexity. CoRR abs/0912.0568 (2009) - [i12]Paul Beame, Trinh Huynh:
Hardness Amplification in Proof Complexity. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c46]Paul Beame
, Dang-Trinh Huynh-Ngoc:
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. FOCS 2008: 499-508 - [i11]Paul Beame, Dang-Trinh Huynh-Ngoc:
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. Electron. Colloquium Comput. Complex. TR08 (2008) - [i10]Paul Beame, Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity of AC^0. Electron. Colloquium Comput. Complex. TR08 (2008) - [i9]Paul Beame, Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity and Threshold Circuit Size of AC^0. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j30]Paul Beame
, Russell Impagliazzo
, Ashish Sabharwal:
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Comput. Complex. 16(3): 245-297 (2007) - [j29]Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. SIAM J. Comput. 37(3): 845-869 (2007) - [c45]Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel:
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. ICALP 2007: 134-145 - [c44]Tian Sang, Paul Beame, Henry A. Kautz:
A Dynamic Approach for MPE and Weighted MAX-SAT. IJCAI 2007: 173-179 - [c43]Paul Beame
, T. S. Jayram, Atri Rudra:
Lower bounds for randomized read/write stream algorithms. STOC 2007: 689-698 - 2006
- [j28]Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson:
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. Comput. Complex. 15(4): 391-432 (2006) - [i8]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j27]Paul Beame
, Joseph C. Culberson, David G. Mitchell, Cristopher Moore
:
The resolution complexity of random graph k-colorability. Discret. Appl. Math. 153(1-3): 25-47 (2005) - [c42]Tian Sang, Paul Beame, Henry A. Kautz:
Performing Bayesian Inference by Weighted Model Counting. AAAI 2005: 475-482 - [c41]Paul Beame
, Toniann Pitassi, Nathan Segerlind, Avi Wigderson:
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. CCC 2005: 52-66 - [c40]Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. ICALP 2005: 1176-1188 - [c39]Tian Sang, Paul Beame
, Henry A. Kautz:
Heuristics for Fast Exact Model Counting. SAT 2005: 226-240 - [i7]Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j26]Paul Beame
, Henry A. Kautz, Ashish Sabharwal:
Towards Understanding and Harnessing the Potential of Clause Learning. J. Artif. Intell. Res. 22: 319-351 (2004) - [j25]Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy:
A sharp threshold in proof complexity yields lower bounds for satisfiability search. J. Comput. Syst. Sci. 68(2): 238-268 (2004) - [j24]Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz
, Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. SIAM J. Comput. 34(2): 261-276 (2004) - [c38]Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi:
Combining Component Caching and Clause Learning for Effective Model Counting. SAT 2004 - [c37]Dimitris Achlioptas, Paul Beame, Michael Molloy:
Exponential bounds for DPLL below the satisfiability threshold. SODA 2004: 139-140 - [p2]Paul Beame
:
Proof complexity. Computational Complexity Theory 2004: 199-246 - [i6]Paul Beame, Joseph C. Culberson, David G. Mitchell, Cristopher Moore:
The Resolution Complexity of Random Graph k-Colorability. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j23]Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM 50(2): 154-195 (2003) - [c36]Paul Beame
, Russell Impagliazzo
, Toniann Pitassi, Nathan Segerlind:
Memoization and DPLL: Formula Caching Proof Systems. CCC 2003: 248- - [c35]Paul Beame, Henry A. Kautz, Ashish Sabharwal:
Understanding the Power of Clause Learning. IJCAI 2003: 1194-1201 - [c34]Ashish Sabharwal, Paul Beame
, Henry A. Kautz:
Using Problem Structure for Efficient Clause Learning. SAT 2003: 242-256 - 2002
- [j22]Paul Beame
, Faith E. Fich:
Optimal Bounds for the Predecessor Problem and Related Problems. J. Comput. Syst. Sci. 65(1): 38-72 (2002) - [j21]Paul Beame
, Richard M. Karp, Toniann Pitassi, Michael E. Saks:
The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. 31(4): 1048-1075 (2002) - [c33]Paul Beame
, Erik Vee:
Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. CCC 2002: 18 - [c32]Josh Buresh-Oppenheim, Paul Beame
, Toniann Pitassi, Ran Raz
, Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. FOCS 2002: 583-592 - [c31]Paul Beame
, Erik Vee:
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. STOC 2002: 688-697 - [i5]Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j20]Paul Beame
, T. S. Jayram, Michael E. Saks:
Time-Space Tradeoffs for Branching Programs. J. Comput. Syst. Sci. 63(4): 542-572 (2001) - [j19]William Chan, Richard J. Anderson, Paul Beame, David H. Jones, David Notkin, William E. Warner:
Optimizing Symbolic Model Checking for Statecharts. IEEE Trans. Software Eng. 27(2): 170-190 (2001) - [c30]Paul Beame
, Russell Impagliazzo
, Ashish Sabharwal:
Resolution Complexity of Independent Sets in Random Graphs. CCC 2001: 52-68 - [c29]Dimitris Achlioptas, Paul Beame
, Michael S. O. Molloy:
A sharp threshold in proof complexity. STOC 2001: 337-346 - [p1]Paul Beame, Toniann Pitassi:
Propositional Proof Complexity: Past, Present, and Future. Current Trends in Theoretical Computer Science 2001: 42-70 - 2000
- [c28]Paul Beame
, Michael E. Saks, Xiaodong Sun, Erik Vee:
Super-linear time-space tradeoff lower bounds for randomized computation. FOCS 2000: 169-179 - [i4]Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j18]Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo
, Martin Tompa:
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. SIAM J. Comput. 28(3): 1051-1072 (1999) - [c27]Richard J. Anderson, Paul Beame, William Chan, David Notkin:
Experiences with the Application of Symbolic Model Checking to the Analysis of Software Specifications. Ershov Memorial Conference 1999: 460-469