Follow
Richard Beigel
Richard Beigel
Verified email at temple.edu
Title
Cited by
Cited by
Year
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
299*1995
On ACC (circuit complexity)
R Beigel, J Tarui
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium …, 1991
273*1991
The expressive power of voting polynomials
J Aspnes, R Beigel, M Furst, S Rudich
Combinatorica 14 (2), 135-148, 1994
2711994
OC1: A randomized algorithm for building oblique decision trees
SK Murthy, S Kasif, S Salzberg, R Beigel
Proceedings of AAAI 93, 322-327, 1993
2591993
PP is closed under intersection
R Beigel, N Reingold, D Spielman
Journal of Computer and System Sciences 50 (2), 191-202, 1995
243*1995
The polynomial method in circuit complexity
R Beigel
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth …, 1993
2141993
3-coloring in time O (1.3289 n)
R Beigel, D Eppstein
Journal of Algorithms 54 (2), 168-204, 2005
1982005
Bounded queries to SAT and the Boolean hierarchy
R Beigel
Theoretical Computer Science 84 (2), 199-223, 1991
1911991
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
1501992
Finding maximum independent sets in sparse and general graphs
R Beigel
SODA 99, 856-857, 1999
1471999
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
1381990
Perceptrons, PP, and the polynomial hierarchy
R Beigel
Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh …, 1992
1281992
Approximable sets
R Beigel, M Kummer, F Stephan
Information and Computation 120 (2), 304-314, 1995
1231995
Representing Boolean functions as polynomials modulo composite numbers
DAM Barrington, R Beigel, S Rudich
Computational Complexity 4 (4), 367-382, 1994
1211994
Learning a hidden matching
N Alon, R Beigel, S Kasif, S Rudich, B Sudakov
SIAM Journal on Computing 33 (2), 487-501, 2004
1122004
Query-limited reducibilities
R Beigel
stanford university, 1988
1101988
Terse, superterse, and verbose sets
R Beigel, WI Gasarch, J Gill, JC Owings
Information and Computation 103 (1), 68-85, 1993
1011993
Counting classes: Thresholds, parity, mods, and fewness
R Beigel, J Gill, U Hertramp
STACS 90, 49-57, 1990
981990
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
911992
The system can't perform the operation now. Try again later.
Articles 1–20