dblp.uni-trier.dewww.uni-trier.de

Paul Beame Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
88EEPaul Beame, Amit Chakrabarti: Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. Computational Complexity 18(2): 169-170 (2009)
2008
87EEPaul Beame, Dang-Trinh Huynh-Ngoc: On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. FOCS 2008: 499-508
86EEPaul 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)
85EEPaul Beame, Dang-Trinh Huynh-Ngoc: Multiparty Communication Complexity of AC^0. Electronic Colloquium on Computational Complexity (ECCC) 15(061): (2008)
84EEPaul 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
83EEPaul Beame, Matei David, Toniann Pitassi, Philipp Woelfel: Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. ICALP 2007: 134-145
82EETian Sang, Paul Beame, Henry A. Kautz: A Dynamic Approach for MPE and Weighted MAX-SAT. IJCAI 2007: 173-179
81EEPaul Beame, T. S. Jayram, Atri Rudra: Lower bounds for randomized read/write stream algorithms. STOC 2007: 689-698
80EEPaul Beame, Russell Impagliazzo, Ashish Sabharwal: The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Computational Complexity 16(3): 245-297 (2007)
79EEPaul 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
78EEPaul 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)
77EEPaul 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
75EEPaul Beame, Toniann Pitassi, Nathan Segerlind: Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. ICALP 2005: 1176-1188
74EEPaul 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
73EETian Sang, Paul Beame, Henry A. Kautz: Heuristics for Fast Exact Model Counting. SAT 2005: 226-240
72EEPaul 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)
71EEPaul 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
70EETian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi: Combining Component Caching and Clause Learning for Effective Model Counting. SAT 2004
69EEDimitris Achlioptas, Paul Beame, Michael Molloy: Exponential bounds for DPLL below the satisfiability threshold. SODA 2004: 139-140
68EEPaul 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)
67EEPaul Beame, Henry A. Kautz, Ashish Sabharwal: Towards Understanding and Harnessing the Potential of Clause Learning. J. Artif. Intell. Res. (JAIR) 22: 319-351 (2004)
66EEDimitris 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)
65EEJoshua 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
64EEPaul 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
62EEAshish Sabharwal, Paul Beame, Henry A. Kautz: Using Problem Structure for Efficient Clause Learning. SAT 2003: 242-256
61EEPaul 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
60EEJosh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal: Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. FOCS 2002: 583-592
59EEPaul Beame, Erik Vee: Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. IEEE Conference on Computational Complexity 2002: 18
58EEPaul Beame, Erik Vee: Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. STOC 2002: 688-697
57EEJosh 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)
56EEPaul Beame, Faith E. Fich: Optimal Bounds for the Predecessor Problem and Related Problems. J. Comput. Syst. Sci. 65(1): 38-72 (2002)
55EEPaul 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
54EEPaul Beame, Russell Impagliazzo, Ashish Sabharwal: Resolution Complexity of Independent Sets in Random Graphs. IEEE Conference on Computational Complexity 2001: 52-68
53EEDimitris 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
51EEWilliam 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)
50EEPaul 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
48EEPaul 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
47EERichard 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
46EEWilliam 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
45EEPaul 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
43EEPaul Beame, Michael E. Saks, Jayram S. Thathachar: Time-Space Tradeoffs for Branching Programs. FOCS 1998: 254-263
42EEWilliam Chan, Richard J. Anderson, Paul Beame, David Notkin: Improving Efficiency of Symbolic Model Checking for State-Based System Requirements. ISSTA 1998: 102-112
41EEPaul 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)
39EEPaul Beame, Russell Impagliazzo, Toniann Pitassi: Improved Depth Lower Bounds for Small Distance Connectivity. Computational Complexity 7(4): 325-345 (1998)
38EEPaul Beame, Faith E. Fich: On Searching Sorted Lists: A Near-Optimal Lower Bound Electronic Colloquium on Computational Complexity (ECCC) 5(28): (1998)
37EEPaul Beame, Michael E. Saks, Jayram S. Thathachar: Time-Space Tradeoffs for Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 5(53): (1998)
36EEPaul Beame, Toniann Pitassi: Propositional Proof Complexity: Past, Present and Future Electronic Colloquium on Computational Complexity (ECCC) 5(67): (1998)
35EEWilliam 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
33EEWilliam 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
30EERichard 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
25EEPaul 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
11EERichard J. Anderson, Paul Beame, Erik Brisson: Parallel Algorithms for Arrangements. SPAA 1990: 298-306
10EERichard J. Anderson, Paul Beame, Walter L. Ruzzo: Low Overhead Parallel Schedules for Task Graphs. SPAA 1990: 66-75
9EEPaul Beame: Lower bounds for recognizing small cliques on CRCW PRAM's. Discrete Applied Mathematics 29(1): 3-20 (1990)
1989
8EEPaul 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
6EEPaul 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

Coauthor Index

1Dimitris Achlioptas [53] [66] [69]
2Richard J. Anderson [10] [11] [29] [30] [33] [35] [42] [46] [47] [51]
3Fahiem Bacchus [70]
4Hans L. Bodlaender [8]
5Allan Borodin [13] [27] [44]
6Erik Brisson [11] [16] [29]
7Joshua Buresh-Oppenheim (Josh Buresh-Oppenheim) [57] [60] [65]
8Steve Burns [30] [35]
9Amit Chakrabarti [88]
10William Chan [30] [33] [35] [42] [46] [47] [51]
11Stephen A. Cook [1] [2] [25] [34]
12Joseph C. Culberson [68] [72]
13Matei David [83]
14Jeff Edmonds [25] [34]
15Faith Ellen (Faith Ellen Fich, Faith E. Fich) [20] [32] [38] [45] [56]
16Johan Håstad [4] [6]
17H. James Hoover [1] [2]
18Dang-Trinh Huynh-Ngoc [84] [85] [86] [87]
19Russell Impagliazzo [17] [19] [24] [25] [26] [34] [39] [54] [64] [77] [80]
20T. S. Jayram (Jayram S. Thathachar) [37] [43] [50] [81]
21David H. Jones [46] [51]
22Richard M. Karp [41] [55]
23Henry A. Kautz [62] [63] [67] [70] [73] [76] [82]
24Marcin Kik [23]
25Jan Krajícek [17] [24]
26Miroslaw Kutylowski [23]
27Richard E. Ladner [16]
28Joan Lawry [18]
29Michael Luby [12]
30David G. Mitchell [68] [72]
31Francesmary Modugno [30] [35]
32Michael Molloy (Michael S. O. Molloy) [53] [66] [69]
33Cristopher Moore [68] [72]
34David Notkin [30] [33] [35] [42] [46] [47] [51]
35Toniann Pitassi [17] [19] [21] [24] [25] [26] [28] [31] [34] [36] [39] [40] [41] [52] [55] [57] [60] [64] [65] [70] [71] [74] [75] [77] [78] [79] [83]
36Pavel Pudlák [17] [24]
37Prabhakar Raghavan [13] [27] [44]
38Ran Raz [57] [60] [65]
39Jon Damon Reese [30] [35]
40Atri Rudra [81]
41Walter L. Ruzzo [10] [13] [27] [44]
42Ashish Sabharwal [54] [57] [60] [62] [63] [65] [67] [80]
43Michael E. Saks [37] [41] [43] [48] [49] [50] [55] [61]
44Tian Sang [70] [73] [76] [82]
45Nathan Segerlind [64] [71] [74] [75] [77] [78] [79]
46Rakesh K. Sinha [20] [32]
47Xiaodong Sun [48] [49] [61]
48Martin Tompa [13] [14] [22] [27] [44]
49Erik Vee [48] [49] [58] [59] [61]
50William E. Warner [46] [51]
51Avi Wigderson [74] [78]
52Philipp Woelfel [83]
53Alan R. Woods [17]
54Peiyuan Yan [14] [22]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)