3-coloring in time 0 (1.3446/sup n/): a no-MIS algorithm R Beigel, D Eppstein Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium …, 1995 | 301* | 1995 |
On ACC (circuit complexity) R Beigel, J Tarui Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium …, 1991 | 277* | 1991 |
The expressive power of voting polynomials J Aspnes, R Beigel, M Furst, S Rudich Combinatorica 14 (2), 135-148, 1994 | 273 | 1994 |
OC1: A randomized algorithm for building oblique decision trees SK Murthy, S Kasif, S Salzberg, R Beigel Proceedings of AAAI 93, 322-327, 1993 | 264 | 1993 |
PP is closed under intersection R Beigel, N Reingold, D Spielman Journal of Computer and System Sciences 50 (2), 191-202, 1995 | 248* | 1995 |
The polynomial method in circuit complexity R Beigel Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth …, 1993 | 221 | 1993 |
3-coloring in time O (1.3289 n) R Beigel, D Eppstein Journal of Algorithms 54 (2), 168-204, 2005 | 197 | 2005 |
Bounded queries to SAT and the Boolean hierarchy R Beigel Theoretical Computer Science 84 (2), 199-223, 1991 | 195 | 1991 |
Representing Boolean functions as polynomials modulo composite numbers DA Mix Barrington, R Beigel, S Rudich Proceedings of the twenty-fourth annual ACM symposium on Theory of computing …, 1992 | 155 | 1992 |
Finding maximum independent sets in sparse and general graphs R Beigel SODA 99, 856-857, 1999 | 149 | 1999 |
Some connections between bounded query classes and nonuniform complexity A Amir, R Beigel, WI Gasarch Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual …, 1990 | 135 | 1990 |
Perceptrons, PP, and the polynomial hierarchy R Beigel Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh …, 1992 | 133 | 1992 |
Representing Boolean functions as polynomials modulo composite numbers DAM Barrington, R Beigel, S Rudich Computational Complexity 4 (4), 367-382, 1994 | 125 | 1994 |
Approximable sets R Beigel, M Kummer, F Stephan Information and Computation 120 (2), 304-314, 1995 | 124 | 1995 |
Learning a hidden matching N Alon, R Beigel, S Kasif, S Rudich, B Sudakov SIAM Journal on Computing 33 (2), 487-501, 2004 | 116 | 2004 |
Query-limited reducibilities R Beigel stanford university, 1988 | 109 | 1988 |
Counting classes: Thresholds, parity, mods, and fewness R Beigel, J Gill, U Hertramp STACS 90, 49-57, 1990 | 102 | 1990 |
Terse, superterse, and verbose sets R Beigel, WI Gasarch, J Gill, JC Owings Information and Computation 103 (1), 68-85, 1993 | 101 | 1993 |
NP-hard sets are P-superterse unless R= NP R Beigel | 97* | 1992 |
Counting classes: Thresholds, parity, mods, and fewness R Beigel, J Gill Theoretical Computer Science 103 (1), 3-23, 1992 | 95 | 1992 |