Search the dblp DataBase
Paul Beame :
[Publications ]
[Author Rank by year ]
[Co-authors ]
[Prefers ]
[Cites ]
[Cited by ]
Publications of Author
Richard J. Anderson , Paul Beame , Erik Brisson Parallel Algorithms for Arrangements. [Citation Graph (1, 0)][DBLP ] Algorithmica, 1996, v:15, n:2, pp:104-125 [Journal ] Paul Beame , Stephen A. Cook , H. James Hoover Log Depth Circuits for Division and Related Problems. [Citation Graph (1, 0)][DBLP ] SIAM J. Comput., 1986, v:15, n:4, pp:994-1003 [Journal ] Tian Sang , Paul Beame , Henry A. Kautz Performing Bayesian Inference by Weighted Model Counting. [Citation Graph (0, 0)][DBLP ] AAAI, 2005, pp:475-482 [Conf ] 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. [Citation Graph (0, 0)][DBLP ] CAV, 1997, pp:316-327 [Conf ] Paul Beame , Russell Impagliazzo , Toniann Pitassi , Nathan Segerlind Memoization and DPLL: Formula Caching Proof Systems. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 2003, pp:248-0 [Conf ] Paul Beame , Russell Impagliazzo , Ashish Sabharwal Resolution Complexity of Independent Sets in Random Graphs. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 2001, pp:52-68 [Conf ] Paul Beame , Toniann Pitassi , Nathan Segerlind , Avi Wigderson A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 2005, pp:52-66 [Conf ] Paul Beame , Erik Vee Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 2002, pp:18- [Conf ] Richard J. Anderson , Paul Beame , William Chan , David Notkin Experiences with the Application of Symbolic Model Checking to the Analysis of Software Specifications. [Citation Graph (0, 0)][DBLP ] Ershov Memorial Conference, 1999, pp:460-469 [Conf ] Josh Buresh-Oppenheim , Paul Beame , Toniann Pitassi , Ran Raz , Ashish Sabharwal Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:583-592 [Conf ] Paul Beame , Allan Borodin , Prabhakar Raghavan , Walter L. Ruzzo , Martin Tompa Time-Space Tradeoffs for Undirected Graph Traversal [Citation Graph (0, 0)][DBLP ] FOCS, 1990, pp:429-438 [Conf ] Paul Beame , Stephen A. Cook , H. James Hoover Log Depth Circuits for Division and Related Problems [Citation Graph (0, 0)][DBLP ] FOCS, 1984, pp:1-6 [Conf ] Paul Beame , Russell Impagliazzo , Jan Krajícek , Toniann Pitassi , Pavel Pudlák Lower Bound on Hilbert's Nullstellensatz and propositional proofs [Citation Graph (0, 0)][DBLP ] FOCS, 1994, pp:794-806 [Conf ] Paul Beame , Russell Impagliazzo , Toniann Pitassi Improved Depth Lower Vounds for Small Distance Connectivity. [Citation Graph (0, 0)][DBLP ] FOCS, 1995, pp:692-701 [Conf ] Paul Beame , Toniann Pitassi Simplified and Improved Resolution Lower Bounds. [Citation Graph (0, 0)][DBLP ] FOCS, 1996, pp:274-282 [Conf ] Paul Beame , Michael E. Saks , Xiaodong Sun , Erik Vee Super-linear time-space tradeoff lower bounds for randomized computation. [Citation Graph (0, 0)][DBLP ] FOCS, 2000, pp:169-179 [Conf ] Paul Beame , Michael E. Saks , Jayram S. Thathachar Time-Space Tradeoffs for Branching Programs. [Citation Graph (0, 0)][DBLP ] FOCS, 1998, pp:254-263 [Conf ] Paul Beame , Martin Tompa , Peiyuan Yan Communication-Space Tradeoffs for Unrestricted Protocols [Citation Graph (0, 0)][DBLP ] FOCS, 1990, pp:420-428 [Conf ] Paul Beame , Toniann Pitassi , Nathan Segerlind Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. [Citation Graph (0, 0)][DBLP ] ICALP, 2005, pp:1176-1188 [Conf ] 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. [Citation Graph (0, 0)][DBLP ] ICSE, 1999, pp:142-151 [Conf ] Paul Beame , Henry A. Kautz , Ashish Sabharwal Understanding the Power of Clause Learning. [Citation Graph (0, 0)][DBLP ] IJCAI, 2003, pp:1194-1201 [Conf ] Tian Sang , Paul Beame , Henry A. Kautz A Dynamic Approach for MPE and Weighted MAX-SAT. [Citation Graph (0, 0)][DBLP ] IJCAI, 2007, pp:173-179 [Conf ] William Chan , Richard J. Anderson , Paul Beame , David Notkin Improving Efficiency of Symbolic Model Checking for State-Based System Requirements. [Citation Graph (0, 0)][DBLP ] ISSTA, 1998, pp:102-112 [Conf ] Paul Beame , Toniann Pitassi An Exponential Separation between the Matching Principle and the Pigeonhole Principle [Citation Graph (0, 0)][DBLP ] LICS, 1993, pp:308-319 [Conf ] Ashish Sabharwal , Paul Beame , Henry A. Kautz Using Problem Structure for Efficient Clause Learning. [Citation Graph (0, 0)][DBLP ] SAT, 2003, pp:242-256 [Conf ] Tian Sang , Fahiem Bacchus , Paul Beame , Henry A. Kautz , Toniann Pitassi Combining Component Caching and Clause Learning for Effective Model Counting. [Citation Graph (0, 0)][DBLP ] SAT, 2004, pp:- [Conf ] Tian Sang , Paul Beame , Henry A. Kautz Heuristics for Fast Exact Model Counting. [Citation Graph (0, 0)][DBLP ] SAT, 2005, pp:226-240 [Conf ] Richard J. Anderson , Paul Beame , Steve Burns , William Chan , Francesmary Modugno , David Notkin , Jon Damon Reese Model Checking Large Software Specifications. [Citation Graph (0, 0)][DBLP ] SIGSOFT FSE, 1996, pp:156-166 [Conf ] Dimitris Achlioptas , Paul Beame , Michael Molloy Exponential bounds for DPLL below the satisfiability threshold. [Citation Graph (0, 0)][DBLP ] SODA, 2004, pp:139-140 [Conf ] Paul Beame , Michael Luby Parallel Search for Maximal Independence Given Minimal Dependence. [Citation Graph (0, 0)][DBLP ] SODA, 1990, pp:212-218 [Conf ] Richard J. Anderson , Paul Beame , Erik Brisson Parallel Algorithms for Arrangements. [Citation Graph (0, 0)][DBLP ] SPAA, 1990, pp:298-306 [Conf ] Richard J. Anderson , Paul Beame , Walter L. Ruzzo Low Overhead Parallel Schedules for Task Graphs. [Citation Graph (0, 0)][DBLP ] SPAA, 1990, pp:66-75 [Conf ] Paul Beame , Hans L. Bodlaender Distributed Computing on TRansitive Networks: The Thorus. [Citation Graph (0, 0)][DBLP ] STACS, 1989, pp:294-303 [Conf ] Dimitris Achlioptas , Paul Beame , Michael S. O. Molloy A sharp threshold in proof complexity. [Citation Graph (0, 0)][DBLP ] STOC, 2001, pp:337-346 [Conf ] Paul Beame Limits on the Power of Concurrent-Write Parallel Machines [Citation Graph (0, 0)][DBLP ] STOC, 1986, pp:169-176 [Conf ] Paul Beame A General Sequential Time-Space Tradeoff for Finding Unique Elements [Citation Graph (0, 0)][DBLP ] STOC, 1989, pp:197-203 [Conf ] Paul Beame , Stephen A. Cook , Jeff Edmonds , Russell Impagliazzo , Toniann Pitassi The relative complexity of NP search problems. [Citation Graph (0, 0)][DBLP ] STOC, 1995, pp:303-314 [Conf ] Paul Beame , Faith E. Fich Optimal Bounds for the Predecessor Problem. [Citation Graph (0, 0)][DBLP ] STOC, 1999, pp:295-304 [Conf ] Paul Beame , Johan Håstad Optimal Bounds for Decision Problems on the CRCW PRAM [Citation Graph (0, 0)][DBLP ] STOC, 1987, pp:83-93 [Conf ] Paul Beame , Russell Impagliazzo , Jan Krajícek , Toniann Pitassi , Pavel Pudlák , Alan R. Woods Exponential Lower Bounds for the Pigeonhole Principle [Citation Graph (0, 0)][DBLP ] STOC, 1992, pp:200-220 [Conf ] Paul Beame , Richard M. Karp , Toniann Pitassi , Michael E. Saks On the Complexity of Unsatisfiability Proofs for Random k -CNF Formulas. [Citation Graph (0, 0)][DBLP ] STOC, 1998, pp:561-571 [Conf ] Paul Beame , Joan Lawry Randomized versus Nondeterministic Communication Complexity [Citation Graph (0, 0)][DBLP ] STOC, 1992, pp:188-199 [Conf ] Paul Beame , Erik Vee Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. [Citation Graph (0, 0)][DBLP ] STOC, 2002, pp:688-697 [Conf ] Paul Beame , Faith E. Fich , Rakesh K. Sinha Separating the Power of EREW and CREW PRAMs with Small Communication Width. [Citation Graph (0, 0)][DBLP ] WADS, 1993, pp:163-174 [Conf ] Paul Beame , Toniann Pitassi An Exponential Separation Between the Parity Principle and the Pigeonhole Principle. [Citation Graph (0, 0)][DBLP ] Ann. Pure Appl. Logic, 1996, v:80, n:3, pp:195-228 [Journal ] Paul Beame , Russell Impagliazzo , Toniann Pitassi Improved Depth Lower Bounds for Small Distance Connectivity. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1998, v:7, n:4, pp:325-345 [Journal ] Toniann Pitassi , Paul Beame , Russell Impagliazzo Exponential Lower Bounds for the Pigeonhole Principle. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1993, v:3, n:, pp:97-140 [Journal ] Paul Beame , Joseph C. Culberson , David G. Mitchell , Cristopher Moore The resolution complexity of random graph k -colorability. [Citation Graph (0, 0)][DBLP ] Discrete Applied Mathematics, 2005, v:153, n:1-3, pp:25-47 [Journal ] Paul Beame , Toniann Pitassi Propositional Proof Complexity: Past, Present and Future. [Citation Graph (0, 0)][DBLP ] Bulletin of the EATCS, 1998, v:65, n:, pp:66-89 [Journal ] Paul Beame , Michael E. Saks , Xiaodong Sun , Erik Vee Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:25, pp:- [Journal ] Josh Buresh-Oppenheim , Paul Beame , Toniann Pitassi , Ran Raz , Ashish Sabharwal Bounded-depth Frege lower bounds for weaker pigeonhole principles [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:023, pp:- [Journal ] Paul Beame , Joseph C. Culberson , David G. Mitchell , Cristopher Moore The Resolution Complexity of Random Graph k-Colorability [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:012, pp:- [Journal ] Paul Beame , Toniann Pitassi , Nathan Segerlind Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:053, pp:- [Journal ] Paul Beame , Faith E. Fich On Searching Sorted Lists: A Near-Optimal Lower Bound [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:28, pp:- [Journal ] Paul Beame , Toniann Pitassi Propositional Proof Complexity: Past, Present and Future [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:67, pp:- [Journal ] Paul Beame Limits on the Power of Concurrent-Write Parallel Machines [Citation Graph (0, 0)][DBLP ] Inf. Comput., 1988, v:76, n:1, pp:13-28 [Journal ] Paul Beame , Allan Borodin , Prabhakar Raghavan , Walter L. Ruzzo , Martin Tompa Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata. [Citation Graph (0, 0)][DBLP ] Inf. Comput., 1996, v:130, n:2, pp:101-129 [Journal ] Paul Beame , Faith E. Fich , Rakesh K. Sinha Separating the Power of EREW and CREW PRAMs with Small Communication Width. [Citation Graph (0, 0)][DBLP ] Inf. Comput., 1997, v:138, n:1, pp:89-99 [Journal ] Paul Beame , Johan Håstad Optimal bounds for decision problems on the CRCW PRAM. [Citation Graph (0, 0)][DBLP ] J. ACM, 1989, v:36, n:3, pp:643-670 [Journal ] Paul Beame , Michael E. Saks , Xiaodong Sun , Erik Vee Time-space trade-off lower bounds for randomized computation of decision problems. [Citation Graph (0, 0)][DBLP ] J. ACM, 2003, v:50, n:2, pp:154-195 [Journal ] Paul Beame , Henry A. Kautz , Ashish Sabharwal Towards Understanding and Harnessing the Potential of Clause Learning. [Citation Graph (0, 0)][DBLP ] J. Artif. Intell. Res. (JAIR), 2004, v:22, n:, pp:319-351 [Journal ] Dimitris Achlioptas , Paul Beame , Michael S. O. Molloy A sharp threshold in proof complexity yields lower bounds for satisfiability search. [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 2004, v:68, n:2, pp:238-268 [Journal ] Paul Beame , Stephen A. Cook , Jeff Edmonds , Russell Impagliazzo , Toniann Pitassi The Relative Complexity of NP Search Problems. [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 1998, v:57, n:1, pp:3-19 [Journal ] Paul Beame , Faith E. Fich Optimal Bounds for the Predecessor Problem and Related Problems. [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 2002, v:65, n:1, pp:38-72 [Journal ] Paul Beame , T. S. Jayram , Michael E. Saks Time-Space Tradeoffs for Branching Programs. [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 2001, v:63, n:4, pp:542-572 [Journal ] Paul Beame , Miroslaw Kutylowski , Marcin Kik Information Broadcasting by Exclusive-Read Prams. [Citation Graph (0, 0)][DBLP ] Parallel Processing Letters, 1994, v:4, n:, pp:159-169 [Journal ] Paul Beame A General Sequential Time-Space Tradeoff for Finding Unique Elements. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 1991, v:20, n:2, pp:270-277 [Journal ] Paul Beame , Allan Borodin , Prabhakar Raghavan , Walter L. Ruzzo , Martin Tompa A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 1999, v:28, n:3, pp:1051-1072 [Journal ] Paul Beame , Richard M. Karp , Toniann Pitassi , Michael E. Saks The Efficiency of Resolution and Davis--Putnam Procedures. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 2002, v:31, n:4, pp:1048-1075 [Journal ] Paul Beame , Martin Tompa , Peiyuan Yan Communication-Space Tradeoffs for Unrestricted Protocols. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 1994, v:23, n:3, pp:652-661 [Journal ] Joshua Buresh-Oppenheim , Paul Beame , Toniann Pitassi , Ran Raz , Ashish Sabharwal Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 2004, v:34, n:2, pp:261-276 [Journal ] Paul Beame , Erik Brisson , Richard E. Ladner The Complexity of Computing Symmetric Functions Using Threshold Circuits. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 1992, v:100, n:1, pp:253-0 [Journal ] William Chan , Richard J. Anderson , Paul Beame , Steve Burns , Francesmary Modugno , David Notkin , Jon Damon Reese Model Checking Large Software Specifications. [Citation Graph (0, 0)][DBLP ] IEEE Trans. Software Eng., 1998, v:24, n:7, pp:498-520 [Journal ] William Chan , Richard J. Anderson , Paul Beame , David H. Jones , David Notkin , William E. Warner Optimizing Symbolic Model Checking for Statecharts. [Citation Graph (0, 0)][DBLP ] IEEE Trans. Software Eng., 2001, v:27, n:2, pp:170-190 [Journal ] Paul Beame , Matei David , Toniann Pitassi , Philipp Woelfel Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. [Citation Graph (0, 0)][DBLP ] ICALP, 2007, pp:134-145 [Conf ] Paul Beame , T. S. Jayram , Atri Rudra Lower bounds for randomized read/write stream algorithms. [Citation Graph (0, 0)][DBLP ] STOC, 2007, pp:689-698 [Conf ] Paul Beame , Toniann Pitassi , Nathan Segerlind , Avi Wigderson A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 2006, v:15, n:4, pp:391-432 [Journal ] Paul Beame , Toniann Pitassi , Nathan Segerlind Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 2007, v:37, n:3, pp:845-869 [Journal ] On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. [Citation Graph (, )][DBLP ] Multiparty Communication Complexity and Threshold Circuit Size of AC^0. [Citation Graph (, )][DBLP ] Hardness amplification in proof complexity. [Citation Graph (, )][DBLP ] The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. [Citation Graph (, )][DBLP ] Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. [Citation Graph (, )][DBLP ] Hardness Amplification in Proof Complexity [Citation Graph (, )][DBLP ] The Quantum Query Complexity of AC0 [Citation Graph (, )][DBLP ] Lower bounds for recognizing small cliques on CRCW PRAM's. [Citation Graph (, )][DBLP ] On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. [Citation Graph (, )][DBLP ] Multiparty Communication Complexity and Threshold Circuit Size of AC^0. [Citation Graph (, )][DBLP ] Multiparty Communication Complexity of AC^0. [Citation Graph (, )][DBLP ] Formula Caching in DPLL. [Citation Graph (, )][DBLP ] Search in 0.007secs, Finished in 0.011secs