| 2008 |
|---|
| 87 | EE | Paul Beame,
Dang-Trinh Huynh-Ngoc:
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments.
FOCS 2008: 499-508 |
| 86 | EE | Paul Beame,
Dang-Trinh Huynh-Ngoc:
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments.
Electronic Colloquium on Computational Complexity (ECCC) 15(024): (2008) |
| 85 | EE | Paul Beame,
Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity of AC^0.
Electronic Colloquium on Computational Complexity (ECCC) 15(061): (2008) |
| 84 | EE | Paul Beame,
Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity and Threshold Circuit Size of AC^0.
Electronic Colloquium on Computational Complexity (ECCC) 15(082): (2008) |
| 2007 |
|---|
| 83 | EE | Paul Beame,
Matei David,
Toniann Pitassi,
Philipp Woelfel:
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.
ICALP 2007: 134-145 |
| 82 | EE | Tian Sang,
Paul Beame,
Henry A. Kautz:
A Dynamic Approach for MPE and Weighted MAX-SAT.
IJCAI 2007: 173-179 |
| 81 | EE | Paul Beame,
T. S. Jayram,
Atri Rudra:
Lower bounds for randomized read/write stream algorithms.
STOC 2007: 689-698 |
| 80 | EE | Paul Beame,
Russell Impagliazzo,
Ashish Sabharwal:
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.
Computational Complexity 16(3): 245-297 (2007) |
| 79 | EE | 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) |
| 2006 |
|---|
| 78 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Computational Complexity 15(4): 391-432 (2006) |
| 77 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Formula Caching in DPLL.
Electronic Colloquium on Computational Complexity (ECCC) 13(140): (2006) |
| 2005 |
|---|
| 76 | | Tian Sang,
Paul Beame,
Henry A. Kautz:
Performing Bayesian Inference by Weighted Model Counting.
AAAI 2005: 475-482 |
| 75 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
ICALP 2005: 1176-1188 |
| 74 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
IEEE Conference on Computational Complexity 2005: 52-66 |
| 73 | EE | Tian Sang,
Paul Beame,
Henry A. Kautz:
Heuristics for Fast Exact Model Counting.
SAT 2005: 226-240 |
| 72 | EE | Paul Beame,
Joseph C. Culberson,
David G. Mitchell,
Cristopher Moore:
The resolution complexity of random graph k-colorability.
Discrete Applied Mathematics 153(1-3): 25-47 (2005) |
| 71 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity
Electronic Colloquium on Computational Complexity (ECCC)(053): (2005) |
| 2004 |
|---|
| 70 | EE | Tian Sang,
Fahiem Bacchus,
Paul Beame,
Henry A. Kautz,
Toniann Pitassi:
Combining Component Caching and Clause Learning for Effective Model Counting.
SAT 2004 |
| 69 | EE | Dimitris Achlioptas,
Paul Beame,
Michael Molloy:
Exponential bounds for DPLL below the satisfiability threshold.
SODA 2004: 139-140 |
| 68 | EE | Paul Beame,
Joseph C. Culberson,
David G. Mitchell,
Cristopher Moore:
The Resolution Complexity of Random Graph k-Colorability
Electronic Colloquium on Computational Complexity (ECCC)(012): (2004) |
| 67 | EE | Paul Beame,
Henry A. Kautz,
Ashish Sabharwal:
Towards Understanding and Harnessing the Potential of Clause Learning.
J. Artif. Intell. Res. (JAIR) 22: 319-351 (2004) |
| 66 | EE | 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) |
| 65 | EE | 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) |
| 2003 |
|---|
| 64 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Memoization and DPLL: Formula Caching Proof Systems.
IEEE Conference on Computational Complexity 2003: 248- |
| 63 | | Paul Beame,
Henry A. Kautz,
Ashish Sabharwal:
Understanding the Power of Clause Learning.
IJCAI 2003: 1194-1201 |
| 62 | EE | Ashish Sabharwal,
Paul Beame,
Henry A. Kautz:
Using Problem Structure for Efficient Clause Learning.
SAT 2003: 242-256 |
| 61 | EE | 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) |
| 2002 |
|---|
| 60 | EE | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
FOCS 2002: 583-592 |
| 59 | EE | Paul Beame,
Erik Vee:
Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems.
IEEE Conference on Computational Complexity 2002: 18 |
| 58 | EE | Paul Beame,
Erik Vee:
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems.
STOC 2002: 688-697 |
| 57 | EE | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles
Electronic Colloquium on Computational Complexity (ECCC)(023): (2002) |
| 56 | EE | Paul Beame,
Faith E. Fich:
Optimal Bounds for the Predecessor Problem and Related Problems.
J. Comput. Syst. Sci. 65(1): 38-72 (2002) |
| 55 | EE | 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) |
| 2001 |
|---|
| 54 | EE | Paul Beame,
Russell Impagliazzo,
Ashish Sabharwal:
Resolution Complexity of Independent Sets in Random Graphs.
IEEE Conference on Computational Complexity 2001: 52-68 |
| 53 | EE | Dimitris Achlioptas,
Paul Beame,
Michael S. O. Molloy:
A sharp threshold in proof complexity.
STOC 2001: 337-346 |
| 52 | | Paul Beame,
Toniann Pitassi:
Propositional Proof Complexity: Past, Present, and Future.
Current Trends in Theoretical Computer Science 2001: 42-70 |
| 51 | EE | 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) |
| 50 | EE | Paul Beame,
T. S. Jayram,
Michael E. Saks:
Time-Space Tradeoffs for Branching Programs.
J. Comput. Syst. Sci. 63(4): 542-572 (2001) |
| 2000 |
|---|
| 49 | | Paul Beame,
Michael E. Saks,
Xiaodong Sun,
Erik Vee:
Super-linear time-space tradeoff lower bounds for randomized computation.
FOCS 2000: 169-179 |
| 48 | EE | Paul Beame,
Michael E. Saks,
Xiaodong Sun,
Erik Vee:
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation
Electronic Colloquium on Computational Complexity (ECCC) 7(25): (2000) |
| 1999 |
|---|
| 47 | EE | 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 |
| 46 | EE | 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 |
| 45 | EE | Paul Beame,
Faith E. Fich:
Optimal Bounds for the Predecessor Problem.
STOC 1999: 295-304 |
| 44 | | 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) |
| 1998 |
|---|
| 43 | EE | Paul Beame,
Michael E. Saks,
Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs.
FOCS 1998: 254-263 |
| 42 | EE | William Chan,
Richard J. Anderson,
Paul Beame,
David Notkin:
Improving Efficiency of Symbolic Model Checking for State-Based System Requirements.
ISSTA 1998: 102-112 |
| 41 | EE | 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 |
| 40 | | Paul Beame,
Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future.
Bulletin of the EATCS 65: 66-89 (1998) |
| 39 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi:
Improved Depth Lower Bounds for Small Distance Connectivity.
Computational Complexity 7(4): 325-345 (1998) |
| 38 | EE | Paul Beame,
Faith E. Fich:
On Searching Sorted Lists: A Near-Optimal Lower Bound
Electronic Colloquium on Computational Complexity (ECCC) 5(28): (1998) |
| 37 | EE | Paul Beame,
Michael E. Saks,
Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs
Electronic Colloquium on Computational Complexity (ECCC) 5(53): (1998) |
| 36 | EE | Paul Beame,
Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future
Electronic Colloquium on Computational Complexity (ECCC) 5(67): (1998) |
| 35 | EE | 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) |
| 34 | | 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) |
| 1997 |
|---|
| 33 | | 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 |
| 32 | | 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) |
| 1996 |
|---|
| 31 | | Paul Beame,
Toniann Pitassi:
Simplified and Improved Resolution Lower Bounds.
FOCS 1996: 274-282 |
| 30 | EE | 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 |
| 29 | | Richard J. Anderson,
Paul Beame,
Erik Brisson:
Parallel Algorithms for Arrangements.
Algorithmica 15(2): 104-125 (1996) |
| 28 | | Paul Beame,
Toniann Pitassi:
An Exponential Separation Between the Parity Principle and the Pigeonhole Principle.
Ann. Pure Appl. Logic 80(3): 195-228 (1996) |
| 27 | | 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) |
| 1995 |
|---|
| 26 | | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi:
Improved Depth Lower Vounds for Small Distance Connectivity.
FOCS 1995: 692-701 |
| 25 | EE | Paul Beame,
Stephen A. Cook,
Jeff Edmonds,
Russell Impagliazzo,
Toniann Pitassi:
The relative complexity of NP search problems.
STOC 1995: 303-314 |
| 1994 |
|---|
| 24 | | 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 |
| 23 | | Paul Beame,
Miroslaw Kutylowski,
Marcin Kik:
Information Broadcasting by Exclusive-Read Prams.
Parallel Processing Letters 4: 159-169 (1994) |
| 22 | | Paul Beame,
Martin Tompa,
Peiyuan Yan:
Communication-Space Tradeoffs for Unrestricted Protocols.
SIAM J. Comput. 23(3): 652-661 (1994) |
| 1993 |
|---|
| 21 | | Paul Beame,
Toniann Pitassi:
An Exponential Separation between the Matching Principle and the Pigeonhole Principle
LICS 1993: 308-319 |
| 20 | | Paul Beame,
Faith E. Fich,
Rakesh K. Sinha:
Separating the Power of EREW and CREW PRAMs with Small Communication Width.
WADS 1993: 163-174 |
| 19 | | Toniann Pitassi,
Paul Beame,
Russell Impagliazzo:
Exponential Lower Bounds for the Pigeonhole Principle.
Computational Complexity 3: 97-140 (1993) |
| 1992 |
|---|
| 18 | | Paul Beame,
Joan Lawry:
Randomized versus Nondeterministic Communication Complexity
STOC 1992: 188-199 |
| 17 | | 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 |
| 16 | | Paul Beame,
Erik Brisson,
Richard E. Ladner:
The Complexity of Computing Symmetric Functions Using Threshold Circuits.
Theor. Comput. Sci. 100(1): 253- (1992) |
| 1991 |
|---|
| 15 | | Paul Beame:
A General Sequential Time-Space Tradeoff for Finding Unique Elements.
SIAM J. Comput. 20(2): 270-277 (1991) |
| 1990 |
|---|
| 14 | | Paul Beame,
Martin Tompa,
Peiyuan Yan:
Communication-Space Tradeoffs for Unrestricted Protocols
FOCS 1990: 420-428 |
| 13 | | Paul Beame,
Allan Borodin,
Prabhakar Raghavan,
Walter L. Ruzzo,
Martin Tompa:
Time-Space Tradeoffs for Undirected Graph Traversal
FOCS 1990: 429-438 |
| 12 | | Paul Beame,
Michael Luby:
Parallel Search for Maximal Independence Given Minimal Dependence.
SODA 1990: 212-218 |
| 11 | EE | Richard J. Anderson,
Paul Beame,
Erik Brisson:
Parallel Algorithms for Arrangements.
SPAA 1990: 298-306 |
| 10 | EE | Richard J. Anderson,
Paul Beame,
Walter L. Ruzzo:
Low Overhead Parallel Schedules for Task Graphs.
SPAA 1990: 66-75 |
| 9 | EE | Paul Beame:
Lower bounds for recognizing small cliques on CRCW PRAM's.
Discrete Applied Mathematics 29(1): 3-20 (1990) |
| 1989 |
|---|
| 8 | | Paul Beame,
Hans L. Bodlaender:
Distributed Computing on TRansitive Networks: The Thorus.
STACS 1989: 294-303 |
| 7 | | Paul Beame:
A General Sequential Time-Space Tradeoff for Finding Unique Elements
STOC 1989: 197-203 |
| 6 | EE | Paul Beame,
Johan Håstad:
Optimal bounds for decision problems on the CRCW PRAM.
J. ACM 36(3): 643-670 (1989) |
| 1988 |
|---|
| 5 | | Paul Beame:
Limits on the Power of Concurrent-Write Parallel Machines
Inf. Comput. 76(1): 13-28 (1988) |
| 1987 |
|---|
| 4 | | Paul Beame,
Johan Håstad:
Optimal Bounds for Decision Problems on the CRCW PRAM
STOC 1987: 83-93 |
| 1986 |
|---|
| 3 | | Paul Beame:
Limits on the Power of Concurrent-Write Parallel Machines
STOC 1986: 169-176 |
| 2 | | Paul Beame,
Stephen A. Cook,
H. James Hoover:
Log Depth Circuits for Division and Related Problems.
SIAM J. Comput. 15(4): 994-1003 (1986) |
| 1984 |
|---|
| 1 | | Paul Beame,
Stephen A. Cook,
H. James Hoover:
Log Depth Circuits for Division and Related Problems
FOCS 1984: 1-6 |
