Paul Beame: Recent Complexity Papers
Optimal Bounds for the Predecessor Problem STOC 99
Time-Space Tradeoffs for Branching Programs Full
paper. Preliminary version at FOCS 98
Proof Complexity Survey EATCS Bulletin
On the Complexity of Unsatisfiability of Random k-CNF Formulas STOC 98
On Searching Sorted Lists: A Near-Optimal Lower Bound
More on the Relative Strength of Counting Principles
Simplified and Improved Resolution Lower Bounds
FOCS 96
Improved Depth Lower Bounds for Small Distance Connectivity FOCS 95
The Relative Complexity of NP Search Problems STOC 95
Lower Bounds for Hilbert's Nullstellensatz and propositional proofs FOCS 94
A Switching Lemma Primer also dvi format
An Exponential Separation between the Matching
Principle and the Pigeonhole Principle LICS 93
Separating the Power of EREW and CREW PRAMs with Small Communication Width WADS 93
Time-Space Tradeoffs for Undirected Graph Traversal
Paul Beame: Verification Papers
Improving Efficiency of Symbolic Model Checking for State-Based System Requirements
ISSTA 98
Combining Constraint Solving and Symbolic
Model Checking for a Class of Systems with Non-linear Constraints CAV 97
Model Checking Large Software Specifications FSE 96