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. |