default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDPaul 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- [i47]Paul Beame, Niels Kornerup:
Quantum Time-Space Tradeoffs for Matrix Problems. CoRR abs/2401.05321 (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 - [c26]William Chan, Richard J. Anderson, Paul Beame, David H. Jones, David Notkin, William E. Warner:
Decoupling Synchronization from Local Control for Efficient Symbolic Model Checking of Statecharts. ICSE 1999: 142-151 - [c25]Paul Beame, Faith E. Fich:
Optimal Bounds for the Predecessor Problem. STOC 1999: 295-304 - 1998
- [j17]Paul Beame, Russell Impagliazzo, Toniann Pitassi:
Improved Depth Lower Bounds for Small Distance Connectivity. Comput. Complex. 7(4): 325-345 (1998) - [j16]Paul Beame, Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future. Bull. EATCS 65: 66-89 (1998) - [j15]Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi:
The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. 57(1): 3-19 (1998) - [j14]William Chan, Richard J. Anderson, Paul Beame, Steve Burns, Francesmary Modugno, David Notkin, Jon Damon Reese:
Model Checking Large Software Specifications. IEEE Trans. Software Eng. 24(7): 498-520 (1998) - [c24]Paul Beame, Michael E. Saks, Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs. FOCS 1998: 254-263 - [c23]William Chan, Richard J. Anderson, Paul Beame, David Notkin:
Improving Efficiency of Symbolic Model Checking for State-Based System Requirements. ISSTA 1998: 102-112 - [c22]Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks:
On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas. STOC 1998: 561-571 - [e1]Paul Beame, Samuel R. Buss:
Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 39, DIMACS/AMS 1998, ISBN 978-0-8218-0577-0 [contents] - [i3]Paul Beame, Faith E. Fich:
On Searching Sorted Lists: A Near-Optimal Lower Bound. Electron. Colloquium Comput. Complex. TR98 (1998) - [i2]Paul Beame, Michael E. Saks, Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs. Electron. Colloquium Comput. Complex. TR98 (1998) - [i1]Paul Beame, Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j13]Paul Beame, Faith E. Fich, Rakesh K. Sinha:
Separating the Power of EREW and CREW PRAMs with Small Communication Width. Inf. Comput. 138(1): 89-99 (1997) - [c21]William Chan, Richard J. Anderson, Paul Beame, David Notkin:
Combining Constraint Solving and Symbolic Model Checking for a Class of a Systems with Non-linear Constraints. CAV 1997: 316-327 - 1996
- [j12]Richard J. Anderson, Paul Beame, Erik Brisson:
Parallel Algorithms for Arrangements. Algorithmica 15(2): 104-125 (1996) - [j11]Paul Beame, Toniann Pitassi:
An Exponential Separation Between the Parity Principle and the Pigeonhole Principle. Ann. Pure Appl. Log. 80(3): 195-228 (1996) - [j10]Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa:
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata. Inf. Comput. 130(2): 101-129 (1996) - [c20]Paul Beame, Søren Riis:
More on the relative strength of counting principles. Proof Complexity and Feasible Arithmetics 1996: 13-35 - [c19]Paul Beame, Toniann Pitassi:
Simplified and Improved Resolution Lower Bounds. FOCS 1996: 274-282 - [c18]Richard J. Anderson, Paul Beame, Steve Burns, William Chan, Francesmary Modugno, David Notkin, Jon Damon Reese:
Model Checking Large Software Specifications. SIGSOFT FSE 1996: 156-166 - 1995
- [c17]Paul Beame, Russell Impagliazzo, Toniann Pitassi:
Improved Depth Lower Vounds for Small Distance Connectivity. FOCS 1995: 692-701 - [c16]Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi:
The relative complexity of NP search problems. STOC 1995: 303-314 - 1994
- [j9]Paul Beame, Miroslaw Kutylowski, Marcin Kik:
Information Broadcasting by Exclusive-Read Prams. Parallel Process. Lett. 4: 159-169 (1994) - [j8]Paul Beame, Martin Tompa, Peiyuan Yan:
Communication-Space Tradeoffs for Unrestricted Protocols. SIAM J. Comput. 23(3): 652-661 (1994) - [c15]Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák:
Lower Bound on Hilbert's Nullstellensatz and propositional proofs. FOCS 1994: 794-806 - 1993
- [j7]Toniann Pitassi, Paul Beame, Russell Impagliazzo:
Exponential Lower Bounds for the Pigeonhole Principle. Comput. Complex. 3: 97-140 (1993) - [c14]Paul Beame, Toniann Pitassi:
An Exponential Separation between the Matching Principle and the Pigeonhole Principle. LICS 1993: 308-319 - [c13]Paul Beame, Faith E. Fich, Rakesh K. Sinha:
Separating the Power of EREW and CREW PRAMs with Small Communication Width. WADS 1993: 163-174 - 1992
- [j6]Paul Beame, Erik Brisson, Richard E. Ladner:
The Complexity of Computing Symmetric Functions Using Threshold Circuits. Theor. Comput. Sci. 100(1): 253-265 (1992) - [c12]Paul Beame, Joan Lawry:
Randomized versus Nondeterministic Communication Complexity. STOC 1992: 188-199 - [c11]Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods:
Exponential Lower Bounds for the Pigeonhole Principle. STOC 1992: 200-220 - 1991
- [j5]Paul Beame:
A General Sequential Time-Space Tradeoff for Finding Unique Elements. SIAM J. Comput. 20(2): 270-277 (1991) - 1990
- [j4]Paul Beame:
Lower bounds for recognizing small cliques on CRCW PRAM's. Discret. Appl. Math. 29(1): 3-20 (1990) - [c10]Paul Beame, Martin Tompa, Peiyuan Yan:
Communication-Space Tradeoffs for Unrestricted Protocols. FOCS 1990: 420-428 - [c9]Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa:
Time-Space Tradeoffs for Undirected Graph Traversal. FOCS 1990: 429-438 - [c8]Paul Beame, Michael Luby:
Parallel Search for Maximal Independence Given Minimal Dependence. SODA 1990: 212-218 - [c7]Richard J. Anderson, Paul Beame, Walter L. Ruzzo:
Low Overhead Parallel Schedules for Task Graphs. SPAA 1990: 66-75 - [c6]Richard J. Anderson, Paul Beame, Erik Brisson:
Parallel Algorithms for Arrangements. SPAA 1990: 298-306
1980 – 1989
- 1989
- [j3]Paul Beame, Johan Håstad:
Optimal bounds for decision problems on the CRCW PRAM. J. ACM 36(3): 643-670 (1989) - [c5]Paul Beame, Hans L. Bodlaender:
Distributed Computing on TRansitive Networks: The Thorus. STACS 1989: 294-303 - [c4]Paul Beame:
A General Sequential Time-Space Tradeoff for Finding Unique Elements. STOC 1989: 197-203 - 1988
- [j2]Paul Beame:
Limits on the Power of Concurrent-Write Parallel Machines. Inf. Comput. 76(1): 13-28 (1988) - 1987
- [c3]Paul Beame, Johan Håstad:
Optimal Bounds for Decision Problems on the CRCW PRAM. STOC 1987: 83-93 - 1986
- [j1]Paul Beame, Stephen A. Cook, H. James Hoover:
Log Depth Circuits for Division and Related Problems. SIAM J. Comput. 15(4): 994-1003 (1986) - [c2]Paul Beame:
Limits on the Power of Concurrent-Write Parallel Machines. STOC 1986: 169-176 - 1984
- [c1]Paul Beame, Stephen A. Cook, H. James Hoover:
Log Depth Circuits for Division and Related Problems. FOCS 1984: 1-6
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 01:26 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
