Paul Beame

According to our database1, Paul Beame
  • authored at least 144 papers between 1984 and 2018.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2018
Edge Estimation with Independent Set Oracles.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Stabbing Planes.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017
Exact Model Counting of Query Expressions: Limitations of Propositional Methods.
ACM Trans. Database Syst., 2017

Communication Steps for Parallel Query Processing.
J. ACM, 2017

Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Stabbing Planes.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Edge Estimation with Independent Set Oracles.
CoRR, 2017

Stabbing Planes.
CoRR, 2017

Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions.
CoRR, 2017

Towards Verifying Nonlinear Integer Arithmetic.
CoRR, 2017

Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Towards Verifying Nonlinear Integer Arithmetic.
Proceedings of the Computer Aided Verification - 29th International Conference, 2017

2016
Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method.
TOCT, 2016

Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.
SIAM J. Comput., 2016

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

Worst-Case Optimal Algorithms for Parallel Query Processing.
CoRR, 2016

Communication Cost in Parallel Query Processing.
CoRR, 2016

Nondeterminism and an abstract formulation of Nečiporuk's lower bound method.
CoRR, 2016

Worst-Case Optimal Algorithms for Parallel Query Processing.
Proceedings of the 19th International Conference on Database Theory, 2016

2015
Finding the Median (Obliviously) with Bounded Space.
CoRR, 2015

New Limits for Knowledge Compilation and Applications to Exact Model Counting.
CoRR, 2015

New Limits for Knowledge Compilation and Applications to Exact Model Counting.
Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 2015

Symmetric Weighted First-Order Model Counting.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Finding the Median (Obliviously) with Bounded Space.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Skew in Parallel Query Processing.
CoRR, 2014

Symmetric Weighted First-Order Model Counting.
CoRR, 2014

Skew in parallel query processing.
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Counting of Query Expressions: Limitations of Propositional Methods.
Proceedings of the Proc. 17th International Conference on Database Theory (ICDT), 2014

Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution.
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013
Element Distinctness, Frequency Moments, and Sliding Windows.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Model Counting of Query Expressions: Limitations of Propositional Methods.
CoRR, 2013

Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases.
CoRR, 2013

Communication Steps for Parallel Query Processing.
CoRR, 2013

Element Distinctness, Frequency Moments, and Sliding Windows.
CoRR, 2013

Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases.
Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, 2013

Communication steps for parallel query processing.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Element Distinctness, Frequency Moments, and Sliding Windows.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
The Value of Multiple Read/Write Streams for Approximating Frequency Moments.
TOCT, 2012

Multiparty Communication Complexity and Threshold Circuit Size of sfAC0.
SIAM J. Comput., 2012

The quantum query complexity of AC0.
Quantum Information & Computation, 2012

Sliding Windows With Limited Storage.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Sliding Windows with Limited Storage
CoRR, 2012

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT.
Proceedings of the 27th Conference on Computational Complexity, 2012

2011
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Towards Understanding and Harnessing the Potential of Clause Learning
CoRR, 2011

Making Branching Programs Oblivious Requires Superlogarithmic Overhead.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010
Formula Caching in DPLL.
TOCT, 2010

Separating Deterministic from Randomized Multiparty Communication Complexity.
Theory of Computing, 2010

Making RAMs Oblivious Requires Superlogarithmic Overhead.
Electronic Colloquium on Computational Complexity (ECCC), 2010

The Quantum Query Complexity of AC0
CoRR, 2010

Hardness amplification in proof complexity.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009
Hardness Amplification in Proof Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Hardness Amplification in Proof Complexity
CoRR, 2009

Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword.
Computational Complexity, 2009

Multiparty Communication Complexity and Threshold Circuit Size of AC^0.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
Multiparty Communication Complexity and Threshold Circuit Size of AC^0.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Multiparty Communication Complexity of AC^0.
Electronic Colloquium on Computational Complexity (ECCC), 2008

On the Value of Multiple Read/Write Streams for Approximating Frequency Moments.
Electronic Colloquium on Computational Complexity (ECCC), 2008

On the Value of Multiple Read/Write Streams for Approximating Frequency Moments.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
SIAM J. Comput., 2007

The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.
Computational Complexity, 2007

Lower bounds for randomized read/write stream algorithms.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A Dynamic Approach for MPE and Weighted MAX-SAT.
Proceedings of the IJCAI 2007, 2007

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
Formula Caching in DPLL.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Computational Complexity, 2006

2005
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity
Electronic Colloquium on Computational Complexity (ECCC), 2005

The resolution complexity of random graph k-colorability.
Discrete Applied Mathematics, 2005

Heuristics for Fast Exact Model Counting.
Proceedings of the Theory and Applications of Satisfiability Testing, 2005

Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Performing Bayesian Inference by Weighted Model Counting.
Proceedings of the Proceedings, 2005

2004
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
SIAM J. Comput., 2004

A sharp threshold in proof complexity yields lower bounds for satisfiability search.
J. Comput. Syst. Sci., 2004

Towards Understanding and Harnessing the Potential of Clause Learning.
J. Artif. Intell. Res., 2004

The Resolution Complexity of Random Graph k-Colorability
Electronic Colloquium on Computational Complexity (ECCC), 2004

Exponential bounds for DPLL below the satisfiability threshold.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Combining Component Caching and Clause Learning for Effective Model Counting.
Proceedings of the SAT 2004, 2004

2003
Time-space trade-off lower bounds for randomized computation of decision problems.
J. ACM, 2003

Using Problem Structure for Efficient Clause Learning.
Proceedings of the Theory and Applications of Satisfiability Testing, 2003

Understanding the Power of Clause Learning.
Proceedings of the IJCAI-03, 2003

Memoization and DPLL: Formula Caching Proof Systems.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
The Efficiency of Resolution and Davis--Putnam Procedures.
SIAM J. Comput., 2002

Optimal Bounds for the Predecessor Problem and Related Problems.
J. Comput. Syst. Sci., 2002

Bounded-depth Frege lower bounds for weaker pigeonhole principles
Electronic Colloquium on Computational Complexity (ECCC), 2002

Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Optimizing Symbolic Model Checking for Statecharts.
IEEE Trans. Software Eng., 2001

Time-Space Tradeoffs for Branching Programs.
J. Comput. Syst. Sci., 2001

A sharp threshold in proof complexity.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Resolution Complexity of Independent Sets in Random Graphs.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Propositional Proof Complexity: Past, Present, and Future.
Current Trends in Theoretical Computer Science, 2001

2000
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation
Electronic Colloquium on Computational Complexity (ECCC), 2000

Super-linear time-space tradeoff lower bounds for randomized computation.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata.
SIAM J. Comput., 1999

Optimal Bounds for the Predecessor Problem.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Decoupling Synchronization from Local Control for Efficient Symbolic Model Checking of Statecharts.
Proceedings of the 1999 International Conference on Software Engineering, 1999

Experiences with the Application of Symbolic Model Checking to the Analysis of Software Specifications.
Proceedings of the Perspectives of System Informatics, 1999

1998
Model Checking Large Software Specifications.
IEEE Trans. Software Eng., 1998

The Relative Complexity of NP Search Problems.
J. Comput. Syst. Sci., 1998

Propositional Proof Complexity: Past, Present and Future
Electronic Colloquium on Computational Complexity (ECCC), 1998

Time-Space Tradeoffs for Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 1998

On Searching Sorted Lists: A Near-Optimal Lower Bound
Electronic Colloquium on Computational Complexity (ECCC), 1998

Propositional Proof Complexity: Past, Present and Future.
Bulletin of the EATCS, 1998

Improved Depth Lower Bounds for Small Distance Connectivity.
Computational Complexity, 1998

On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Improving Efficiency of Symbolic Model Checking for State-Based System Requirements.
Proceedings of ACM SIGSOFT International Symposium on Software Testing and Analysis, 1998

Time-Space Tradeoffs for Branching Programs.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Separating the Power of EREW and CREW PRAMs with Small Communication Width.
Inf. Comput., 1997

Combining Constraint Solving and Symbolic Model Checking for a Class of a Systems with Non-linear Constraints.
Proceedings of the Computer Aided Verification, 9th International Conference, 1997

1996
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata.
Inf. Comput., 1996

An Exponential Separation Between the Parity Principle and the Pigeonhole Principle.
Ann. Pure Appl. Logic, 1996

Parallel Algorithms for Arrangements.
Algorithmica, 1996

Model Checking Large Software Specifications.
Proceedings of the SIGSOFT '96, 1996

Simplified and Improved Resolution Lower Bounds.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

More on the relative strength of counting principles.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995
The relative complexity of NP search problems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Improved Depth Lower Vounds for Small Distance Connectivity.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Communication-Space Tradeoffs for Unrestricted Protocols.
SIAM J. Comput., 1994

Information Broadcasting by Exclusive-Read Prams.
Parallel Processing Letters, 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Exponential Lower Bounds for the Pigeonhole Principle.
Computational Complexity, 1993

Separating the Power of EREW and CREW PRAMs with Small Communication Width.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

An Exponential Separation between the Matching Principle and the Pigeonhole Principle
Proceedings of the Eighth Annual Symposium on Logic in Computer Science (LICS '93), 1993

1992
The Complexity of Computing Symmetric Functions Using Threshold Circuits.
Theor. Comput. Sci., 1992

Randomized versus Nondeterministic Communication Complexity
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Exponential Lower Bounds for the Pigeonhole Principle
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991
A General Sequential Time-Space Tradeoff for Finding Unique Elements.
SIAM J. Comput., 1991

1990
Lower bounds for recognizing small cliques on CRCW PRAM's.
Discrete Applied Mathematics, 1990

Low Overhead Parallel Schedules for Task Graphs.
SPAA, 1990

Parallel Algorithms for Arrangements.
SPAA, 1990

Parallel Search for Maximal Independence Given Minimal Dependence.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Communication-Space Tradeoffs for Unrestricted Protocols
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Time-Space Tradeoffs for Undirected Graph Traversal
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Optimal bounds for decision problems on the CRCW PRAM.
J. ACM, 1989

A General Sequential Time-Space Tradeoff for Finding Unique Elements
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Distributed Computing on TRansitive Networks: The Thorus.
Proceedings of the STACS 89, 1989

1988
Limits on the Power of Concurrent-Write Parallel Machines
Inf. Comput., January, 1988

1987
Optimal Bounds for Decision Problems on the CRCW PRAM
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
Log Depth Circuits for Division and Related Problems.
SIAM J. Comput., 1986

Limits on the Power of Concurrent-Write Parallel Machines
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1984
Log Depth Circuits for Division and Related Problems
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984


  Loading...