The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Paul Beame: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. 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]
  2. 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]
  3. 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]
  4. 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]
  5. 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]
  6. 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]
  7. 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]
  8. 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]
  9. 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]
  10. 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]
  11. 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]
  12. 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]
  13. 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]
  14. 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]
  15. Paul Beame, Toniann Pitassi
    Simplified and Improved Resolution Lower Bounds. [Citation Graph (0, 0)][DBLP]
    FOCS, 1996, pp:274-282 [Conf]
  16. 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]
  17. 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]
  18. Paul Beame, Martin Tompa, Peiyuan Yan
    Communication-Space Tradeoffs for Unrestricted Protocols [Citation Graph (0, 0)][DBLP]
    FOCS, 1990, pp:420-428 [Conf]
  19. 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]
  20. 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]
  21. Paul Beame, Henry A. Kautz, Ashish Sabharwal
    Understanding the Power of Clause Learning. [Citation Graph (0, 0)][DBLP]
    IJCAI, 2003, pp:1194-1201 [Conf]
  22. 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]
  23. 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]
  24. 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]
  25. 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]
  26. 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]
  27. Tian Sang, Paul Beame, Henry A. Kautz
    Heuristics for Fast Exact Model Counting. [Citation Graph (0, 0)][DBLP]
    SAT, 2005, pp:226-240 [Conf]
  28. 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]
  29. 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]
  30. Paul Beame, Michael Luby
    Parallel Search for Maximal Independence Given Minimal Dependence. [Citation Graph (0, 0)][DBLP]
    SODA, 1990, pp:212-218 [Conf]
  31. Richard J. Anderson, Paul Beame, Erik Brisson
    Parallel Algorithms for Arrangements. [Citation Graph (0, 0)][DBLP]
    SPAA, 1990, pp:298-306 [Conf]
  32. 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]
  33. Paul Beame, Hans L. Bodlaender
    Distributed Computing on TRansitive Networks: The Thorus. [Citation Graph (0, 0)][DBLP]
    STACS, 1989, pp:294-303 [Conf]
  34. 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]
  35. Paul Beame
    Limits on the Power of Concurrent-Write Parallel Machines [Citation Graph (0, 0)][DBLP]
    STOC, 1986, pp:169-176 [Conf]
  36. Paul Beame
    A General Sequential Time-Space Tradeoff for Finding Unique Elements [Citation Graph (0, 0)][DBLP]
    STOC, 1989, pp:197-203 [Conf]
  37. 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]
  38. Paul Beame, Faith E. Fich
    Optimal Bounds for the Predecessor Problem. [Citation Graph (0, 0)][DBLP]
    STOC, 1999, pp:295-304 [Conf]
  39. 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]
  40. 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]
  41. 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]
  42. Paul Beame, Joan Lawry
    Randomized versus Nondeterministic Communication Complexity [Citation Graph (0, 0)][DBLP]
    STOC, 1992, pp:188-199 [Conf]
  43. 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]
  44. 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]
  45. 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]
  46. 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]
  47. 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]
  48. 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]
  49. 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]
  50. 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]
  51. 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]
  52. 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]
  53. 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]
  54. 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]
  55. 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]
  56. 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]
  57. 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]
  58. 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]
  59. 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]
  60. 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]
  61. 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]
  62. 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]
  63. 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]
  64. 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]
  65. 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]
  66. 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]
  67. 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]
  68. 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]
  69. 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]
  70. 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]
  71. 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]
  72. 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]
  73. 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]
  74. 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]
  75. 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]
  76. 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]
  77. 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]
  78. 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]

  79. On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. [Citation Graph (, )][DBLP]


  80. Multiparty Communication Complexity and Threshold Circuit Size of AC^0. [Citation Graph (, )][DBLP]


  81. Hardness amplification in proof complexity. [Citation Graph (, )][DBLP]


  82. The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. [Citation Graph (, )][DBLP]


  83. Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. [Citation Graph (, )][DBLP]


  84. Hardness Amplification in Proof Complexity [Citation Graph (, )][DBLP]


  85. The Quantum Query Complexity of AC0 [Citation Graph (, )][DBLP]


  86. Lower bounds for recognizing small cliques on CRCW PRAM's. [Citation Graph (, )][DBLP]


  87. On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. [Citation Graph (, )][DBLP]


  88. Multiparty Communication Complexity and Threshold Circuit Size of AC^0. [Citation Graph (, )][DBLP]


  89. Multiparty Communication Complexity of AC^0. [Citation Graph (, )][DBLP]


  90. Formula Caching in DPLL. [Citation Graph (, )][DBLP]


Search in 0.031secs, Finished in 0.033secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002