Date: Tue, 10 Dec 1996 15:20:41 GMT Server: NCSA/1.4.2 Content-type: text/html Last-modified: Sun, 20 Oct 1996 19:41:15 GMT Content-length: 956 Paul Beame: papers

Paul Beame: Selected Recent Papers

  • 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
  • An Exponential Separation between the Matching Principle and the Pigeonhole Principle
  • Separating the Power of EREW and CREW PRAMs with Small Communication Width
  • Time-Space Tradeoffs for Undirected Graph Traversal

  • beame@cs.washington.edu