Paul W. Beame - Publications

Affiliations: 
University of Washington, Seattle, Seattle, WA 
Area:
Computer Science

35 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Beame P, Gharan SO, Yang X. On the Bias of Reed--Muller Codes over Odd Prime Fields Siam Journal On Discrete Mathematics. 34: 1232-1247. DOI: 10.1137/18M1215104  0.378
2019 Beame P, Liew V. Toward Verifying Nonlinear Integer Arithmetic Journal of the Acm. 66: 22. DOI: 10.1145/3319396  0.401
2017 Beame P, Koutris P, Suciu D. Communication Steps for Parallel Query Processing Journal of the Acm. 64: 40. DOI: 10.1145/3125644  0.436
2017 Beame P, Li J, Roy S, Suciu D. Exact Model Counting of Query Expressions Acm Transactions On Database Systems. 42: 1-46. DOI: 10.1145/2984632  0.413
2016 Beame P, Grosshans N, McKenzie P, Segoufin L. Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method Acm Transactions On Computation Theory. 9: 1-34. DOI: 10.1145/3013516  0.458
2012 Beame P, Huynh T. The Value of Multiple Read/Write Streams for Approximating Frequency Moments Acm Transactions On Computation Theory. 3: 6. DOI: 10.1145/2077336.2077339  0.409
2012 Beame P, Beck C, Impagliazzo R. Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear space Proceedings of the Annual Acm Symposium On Theory of Computing. 213-231. DOI: 10.1137/130914085  0.491
2012 Beame P, Huynh T. Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$ Siam Journal On Computing. 41: 484-518. DOI: 10.1137/100792779  0.455
2010 Beame P, David M, Pitassi T, Woelfel P. Separating Deterministic from Randomized Multiparty Communication Complexity Theory of Computing. 6: 201-225. DOI: 10.4086/Toc.2010.V006A009  0.442
2010 Beame P, Impagliazzo R, Pitassi T, Segerlind N. Formula caching in DPLL Acm Transactions On Computation Theory. 1. DOI: 10.1145/1714450.1714452  0.385
2007 Beame P, Impagliazzo R, Sabharwal A. The resolution complexity of independent sets and vertex covers in random graphs Computational Complexity. 16: 245-297. DOI: 10.1007/S00037-007-0230-0  0.65
2006 Beame P, Pitassi T, Segerlind N, Wigderson A. A strong direct product theorem for corruption and the multiparty communication complexity of disjointness Computational Complexity. 15: 391-432. DOI: 10.1007/S00037-007-0220-2  0.464
2005 Beame P, Pitassi T, Segerlind N. Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity Lecture Notes in Computer Science. 3580: 1176-1188. DOI: 10.1137/060654645  0.503
2004 Beame P, Kautz H, Sabharwal A. Towards understanding and harnessing the potential of clause learning Journal of Artificial Intelligence Research. 22: 319-351. DOI: 10.1613/Jair.1410  0.524
2004 Achlioptas D, Beame P, Molloy M. A sharp threshold in proof complexity yields lower bounds for satisfiability search Journal of Computer and System Sciences. 68: 238-268. DOI: 10.1016/J.Jcss.2003.07.011  0.408
2003 Beame P, Saks M, Sun X, Vee E. Time-space trade-off lower bounds for randomized computation of decision problems Journal of the Acm. 50: 154-195. DOI: 10.1145/636865.636867  0.66
2002 Buresh-Oppenheim J, Beame P, Pitassi T, Raz R, Sabharwal A. Bounded-depth Frege lower bounds for weaker pigeonhole principles Annual Symposium On Foundations of Computer Science - Proceedings. 583-592. DOI: 10.1137/S0097539703433146  0.627
2002 Beame P, Karp R, Pitassi T, Saks M. The efficiency of resolution and Davis-Putnam procedures Siam Journal On Computing. 31: 1048-1075. DOI: 10.1137/S0097539700369156  0.517
2001 Beame P, Jayram TS, Saks M. Time-Space Tradeoffs for Branching Programs Journal of Computer and System Sciences. 63: 542-572. DOI: 10.1006/Jcss.2001.1778  0.431
1998 Beame P, Borodin A, Raghavan P, Ruzzo WL, Tompa M. A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata Siam Journal On Computing. 28: 1051-1072. DOI: 10.1137/S0097539793282947  0.38
1998 Beame P, Impagliazzo R, Pitassi T. Improved depth lower bounds for small distance connectivity Computational Complexity. 7: 325-345. DOI: 10.1007/S000370050014  0.453
1998 Beame P, Cook S, Edmonds J, Impagliazzo R, Pitassi T. The Relative Complexity of NP Search Problems Journal of Computer and System Sciences. 57: 3-19. DOI: 10.1006/Jcss.1998.1575  0.374
1997 Beame P, Fich FE, Sinha RK. Separating the power of EREW and CREW PRAMs with small communication width Information & Computation. 138: 89-99. DOI: 10.1006/Inco.1997.2649  0.304
1996 Beame P, Impagliazzo R, Krajíček J, Pitassi T, Pudlák P. Lower bounds on Hilbert's Nullstellensatz and propositional proofs Proceedings of the London Mathematical Society. 73: 1-26. DOI: 10.1112/Plms/S3-73.1.1  0.447
1996 Beame P, Pitassi T. An exponential separation between the parity principle and the pigeonhole principle Annals of Pure and Applied Logic. 80: 195-228. DOI: 10.1016/0168-0072(96)83747-X  0.42
1996 Beame P, Borodin A, Raghavan P, Ruzzo WL, Tompa M. Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata Information and Computation. 130: 101-129. DOI: 10.1006/Inco.1996.0085  0.453
1994 Beame P, Kutylowski M, Kik M. Information Broadcasting By Exclusive-Read Prams Parallel Processing Letters. 4: 159-169. DOI: 10.1142/S012962649400017X  0.37
1994 Beame P, Tompa M, Yan P. Communication-Space Tradeoffs for UnrestrictedProtocols Siam Journal On Computing. 23: 652-661. DOI: 10.1137/S0097539791196883  0.355
1993 Pitassi T, Beame P, Impagliazzo R. Exponential lower bounds for the pigeonhole principle Computational Complexity. 3: 97-140. DOI: 10.1007/Bf01200117  0.541
1992 Beame P, Brisson E, Ladner R. The complexity of computing symmetric functions using threshold circuits Theoretical Computer Science. 100: 253-265. DOI: 10.1016/0304-3975(92)90372-M  0.429
1991 Beame P. A general sequential time-space tradeoff for finding unique elements Siam Journal On Computing. 20: 270-277. DOI: 10.1137/0220017  0.431
1990 Beame P. Lower bounds for recognizing small cliques on CRCW PRAM'S Discrete Applied Mathematics. 29: 3-20. DOI: 10.1016/0166-218X(90)90079-R  0.48
1989 Beame P, Hastad J. Optimal bounds for decision problems on the CRCW PRAM Journal of the Acm. 36: 643-670. DOI: 10.1145/65950.65958  0.545
1988 Beame P. Limits on the power of concurrent-write parallel machines Information & Computation. 76: 13-28. DOI: 10.1016/0890-5401(88)90040-5  0.478
1986 Beame PW, Cook SA, Hoover HJ. Log depth circuits for division and related problems Siam Journal On Computing. 15: 994-1003. DOI: 10.1137/0215070  0.415
Show low-probability matches.