| 2006 |
|---|
| 105 | EE | Richard Beigel,
William I. Gasarch,
James Glenn:
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems.
MFCS 2006: 146-156 |
| 104 | EE | Richard Beigel,
Lance Fortnow,
William I. Gasarch:
A tight lower bound for restricted pir protocols.
Computational Complexity 15(1): 82-91 (2006) |
| 103 | EE | Richard Beigel,
Lance Fortnow,
Frank Stephan:
Infinitely-Often Autoreducible Sets.
SIAM J. Comput. 36(3): 595-608 (2006) |
| 2005 |
|---|
| 102 | EE | Richard Beigel,
David Eppstein:
3-coloring in time O(1.3289n).
J. Algorithms 54(2): 168-204 (2005) |
| 2004 |
|---|
| 101 | EE | Bin Fu,
Richard Beigel:
Diagnosis in the Presence of Intermittent Faults.
ISAAC 2004: 427-441 |
| 100 | EE | Richard Beigel,
Harry Buhrman,
Peter A. Fejer,
Lance Fortnow,
Piotr Grabowski,
Luc Longpré,
Andrei A. Muchnik,
Frank Stephan,
Leen Torenvliet:
Enumerations of the Kolmogorov Function
Electronic Colloquium on Computational Complexity (ECCC)(015): (2004) |
| 99 | EE | Noga Alon,
Richard Beigel,
Simon Kasif,
Steven Rudich,
Benny Sudakov:
Learning a Hidden Matching.
SIAM J. Comput. 33(2): 487-501 (2004) |
| 98 | EE | Vilhelm Dahllöf,
Peter Jonsson,
Richard Beigel:
Algorithms for four variants of the exact satisfiability problem.
Theor. Comput. Sci. 320(2-3): 373-394 (2004) |
| 2003 |
|---|
| 97 | EE | Richard Beigel,
Lance Fortnow:
Are Cook and Karp Ever the Same?
IEEE Conference on Computational Complexity 2003: 333-336 |
| 96 | EE | Richard Beigel,
Lance Fortnow,
Frank Stephan:
Infinitely-Often Autoreducible Sets.
ISAAC 2003: 98-107 |
| 95 | EE | Richard Beigel,
Lance Fortnow,
William I. Gasarch:
A Nearly Tight Bound for Private Information Retrieval Protocols
Electronic Colloquium on Computational Complexity (ECCC)(087): (2003) |
| 94 | EE | Amihood Amir,
Richard Beigel,
William I. Gasarch:
Some connections between bounded query classes and non-uniform complexity.
Inf. Comput. 186(1): 104-139 (2003) |
| 2002 |
|---|
| 93 | EE | Noga Alon,
Richard Beigel,
Simon Kasif,
Steven Rudich,
Benny Sudakov:
Learning a Hidden Matching.
FOCS 2002: 197- |
| 92 | EE | Richard Beigel,
Lane A. Hemaspaandra,
Harald Hempel,
Jörg Vogel:
Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph.
Inf. Comput. 173(2): 123-131 (2002) |
| 2001 |
|---|
| 91 | EE | Noga Alon,
Richard Beigel:
Lower Bounds for Approximations by Low Degree Polynomials Over Zm.
IEEE Conference on Computational Complexity 2001: 184-187 |
| 90 | EE | Richard Beigel,
Noga Alon,
Simon Kasif,
Mehmet Serkan Apaydin,
Lance Fortnow:
An optimal procedure for gap closing in whole genome shotgun sequencing.
RECOMB 2001: 22-30 |
| 89 | | Richard Beigel,
Richard Chang:
Commutative Queries.
Inf. Comput. 166(1): 71-91 (2001) |
| 2000 |
|---|
| 88 | EE | Richard Beigel,
David Eppstein:
3-Coloring in Time O(1.3289^n)
CoRR cs.DS/0006046: (2000) |
| 87 | EE | Amihood Amir,
Richard Beigel,
William I. Gasarch:
Some Connections between Bounded Query Classes and Non-Uniform Complexity
Electronic Colloquium on Computational Complexity (ECCC) 7(24): (2000) |
| 86 | | Richard Beigel,
Bin Fu:
Circuits over PP and PL.
J. Comput. Syst. Sci. 60(2): 422-441 (2000) |
| 85 | | Richard Beigel,
William I. Gasarch,
Martin Kummer,
Georgia Martin,
Timothy McNicholl,
Frank Stephan:
The Comlexity of OddAn.
J. Symb. Log. 65(1): 1-18 (2000) |
| 84 | EE | Vikraman Arvind,
Richard Beigel,
Antoni Lozano:
The Complexity of Modular Graph Automorphism.
SIAM J. Comput. 30(4): 1299-1320 (2000) |
| 1999 |
|---|
| 83 | EE | Richard Beigel:
Gaps in Bounded Query Hierarchies.
IEEE Conference on Computational Complexity 1999: 124-141 |
| 82 | EE | Richard Beigel,
Alexis Maciel:
Circuit Lower Bounds Collapse Relativized Complexity Classes.
IEEE Conference on Computational Complexity 1999: 222-226 |
| 81 | EE | Richard Beigel:
Finding Maximum Independent Sets in Sparse and General Graphs.
SODA 1999: 856-857 |
| 80 | EE | Bin Fu,
Richard Beigel:
A Comparison of Resource-Bounded Molecular Computation Models.
Algorithmica 24(2): 87-95 (1999) |
| 79 | EE | Richard Beigel,
Bin Fu:
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion.
Algorithmica 25(2-3): 222-238 (1999) |
| 78 | | Richard Beigel,
Anna Bernasconi:
A Note on the Polynomial Representation of Boolean Functions over GF(2).
Int. J. Found. Comput. Sci. 10(4): 535- (1999) |
| 1998 |
|---|
| 77 | EE | Richard Beigel,
Bin Fu:
Solving Intractable Problems with DNA Computing.
IEEE Conference on Computational Complexity 1998: 154- |
| 76 | EE | Richard Beigel,
Egemen Tanin:
The Geometry of Browsing.
LATIN 1998: 331-340 |
| 75 | | Vikraman Arvind,
Richard Beigel,
Antoni Lozano:
The Complexity of Modular Graph Automorphism.
STACS 1998: 172-182 |
| 74 | EE | Richard Beigel,
Tirza Hirst:
One Help Bit Doesn't Help.
STOC 1998: 124-130 |
| 73 | EE | Richard Beigel,
Harry Buhrman,
Lance Fortnow:
NP Might Not Be As Easy As Detecting Unique Solutions.
STOC 1998: 203-208 |
| 72 | EE | Richard Beigel:
Gaps in Bounded Query Hierarchies
Electronic Colloquium on Computational Complexity (ECCC) 5(26): (1998) |
| 71 | EE | Richard Beigel,
Judy Goldsmith:
Downward Separation Fails Catastrophically for Limited Nondeterminism Classes.
SIAM J. Comput. 27(5): 1420-1429 (1998) |
| 70 | EE | Richard Beigel,
William I. Gasarch,
Ming Li,
Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis.
Theor. Comput. Sci. 191(1-2): 245-248 (1998) |
| 1997 |
|---|
| 69 | | Richard Beigel,
Bin Fu:
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion.
ICALP 1997: 816-826 |
| 68 | EE | Richard Beigel,
Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes.
IEEE Conference on Computational Complexity 1997: 149-157 |
| 67 | EE | Richard Beigel,
Bin Fu:
Circuits Over PP and PL.
IEEE Conference on Computational Complexity 1997: 24-35 |
| 66 | EE | Egemen Tanin,
Richard Beigel,
Ben Shneiderman:
Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces.
INFOVIS 1997: 81-86 |
| 65 | EE | Richard Beigel:
Closure Properties of GapP and #P.
ISTCS 1997: 144-146 |
| 64 | EE | Richard Beigel,
Richard Chang:
Commutative Queries.
ISTCS 1997: 159-165 |
| 63 | EE | Bin Fu,
Richard Beigel:
A Comparison of Resource-Bounded Molecular Computation Models.
ISTCS 1997: 6-11 |
| 62 | | Richard Beigel,
Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes.
Computational Complexity 6(3): 235-255 (1997) |
| 61 | EE | Richard Beigel,
Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes
Electronic Colloquium on Computational Complexity (ECCC) 4(2): (1997) |
| 1996 |
|---|
| 60 | | Manindra Agrawal,
Richard Beigel,
Thomas Thierauf:
Pinpointing Computation with Modular Queries in the Boolean Hierarchy.
FSTTCS 1996: 322-334 |
| 59 | | Richard Beigel,
William I. Gasarch,
Martin Kummer,
Timothy McNicholl,
Frank Stephan:
On the Query Complexity of Sets.
MFCS 1996: 206-217 |
| 58 | EE | Manindra Agrawal,
Richard Beigel,
Thomas Thierauf:
Modulo Information from Nonadaptive Queries to NP
Electronic Colloquium on Computational Complexity (ECCC) 3(1): (1996) |
| 57 | EE | Richard Beigel,
William I. Gasarch,
Ming Li,
Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis
Electronic Colloquium on Computational Complexity (ECCC) 3(51): (1996) |
| 56 | EE | Egemen Tanin,
Richard Beigel,
Ben Shneiderman:
Incremental data Structures and Algorithms for Dynamic Query Interfaces.
SIGMOD Record 25(4): 21-24 (1996) |
| 55 | EE | Richard Beigel,
William I. Gasarch,
Efim B. Kinber:
Frequency Computation and Bounded Queries.
Theor. Comput. Sci. 163(1&2): 177-192 (1996) |
| 1995 |
|---|
| 54 | | Richard Beigel,
David Eppstein:
3-Coloring in Time O(1.3446n): A No-MIS Algorithm.
FOCS 1995: 444-452 |
| 53 | | Richard Beigel,
William Hurwood,
Nabil Kahale:
Fault Diagnosis in a Flash.
FOCS 1995: 571-580 |
| 52 | | Richard Beigel,
William I. Gasarch,
Efim B. Kinber:
Frequency Computation and Bounded Queries.
Structure in Complexity Theory Conference 1995: 125-132 |
| 51 | | Richard Beigel,
Howard Straubing:
The Power of Local Self-Reductions.
Structure in Complexity Theory Conference 1995: 277-285 |
| 50 | EE | Richard Beigel,
David Eppstein:
3-Coloring in time O(1.3446n): A no-MIS Algorithm
Electronic Colloquium on Computational Complexity (ECCC) 2(33): (1995) |
| 49 | EE | Richard Beigel:
Closure Properties of GapP and #P
Electronic Colloquium on Computational Complexity (ECCC) 2(35): (1995) |
| 48 | EE | Richard Beigel,
William I. Gasarch,
Efim B. Kinber:
Frequency Computation and Bounded Queries
Electronic Colloquium on Computational Complexity (ECCC) 2(36): (1995) |
| 47 | EE | Richard Beigel,
Howard Straubing:
The Power of Local Self-Reductions
Electronic Colloquium on Computational Complexity (ECCC) 2(37): (1995) |
| 46 | | Richard Beigel,
Martin Kummer,
Frank Stephan:
Quantifying the Amount of Verboseness
Inf. Comput. 118(1): 73-90 (1995) |
| 45 | | Richard Beigel,
Martin Kummer,
Frank Stephan:
Approximable Sets
Inf. Comput. 120(2): 304-314 (1995) |
| 44 | | Richard Beigel,
Nick Reingold,
Daniel A. Spielman:
PP Is Closed under Intersection.
J. Comput. Syst. Sci. 50(2): 191-202 (1995) |
| 1994 |
|---|
| 43 | | Ming Gu,
Martin Farach,
Richard Beigel:
An Efficient Algorithm for Dynamic Text Indexing.
SODA 1994: 697-704 |
| 42 | | Richard Beigel,
Martin Kummer,
Frank Stephan:
Approximable Sets.
Structure in Complexity Theory Conference 1994: 12-23 |
| 41 | | Richard Beigel,
Judy Goldsmith:
Downward separation fails catastrophically for limited nondeterminism classes.
Structure in Complexity Theory Conference 1994: 134-138 |
| 40 | | James Aspnes,
Richard Beigel,
Merrick L. Furst,
Steven Rudich:
The Expressive Power of Voting Polynomials.
Combinatorica 14(2): 135-148 (1994) |
| 39 | | Richard Beigel:
When do Extra Majority Gates Help? Polylog(N) Majority Gates Are Equivalent to One.
Computational Complexity 4: 314-324 (1994) |
| 38 | | Richard Beigel:
Perceptrons, PP, and the Polynomial Hierarchy.
Computational Complexity 4: 339-349 (1994) |
| 37 | | Richard Beigel,
Jun Tarui:
On ACC.
Computational Complexity 4: 350-366 (1994) |
| 36 | | David A. Mix Barrington,
Richard Beigel,
Steven Rudich:
Representing Boolean Functions as Polynomials Modulo Composite Numbers.
Computational Complexity 4: 367-382 (1994) |
| 35 | EE | Richard Beigel,
William Hurwood,
Nabil Kahale:
Fault Diagnosis in a Flash
Electronic Colloquium on Computational Complexity (ECCC) 1(11): (1994) |
| 1993 |
|---|
| 34 | | Sreerama K. Murthy,
Simon Kasif,
Steven Salzberg,
Richard Beigel:
OC1: A Randomized Induction of Oblique Decision Trees.
AAAI 1993: 322-327 |
| 33 | EE | Richard Beigel,
Grigorii Margulis,
Daniel A. Spielman:
Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds.
SPAA 1993: 21-29 |
| 32 | | Richard Beigel:
The Polynomial Method in Circuit Complexity.
Structure in Complexity Theory Conference 1993: 82-95 |
| 31 | | Richard Beigel,
William I. Gasarch,
John Gill,
James C. Owings:
Terse, Superterse, and Verbose Sets
Inf. Comput. 103(1): 68-85 (1993) |
| 30 | | Richard Beigel,
Richard Chang,
Mitsunori Ogiwara:
A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies.
Mathematical Systems Theory 26(3): 293-310 (1993) |
| 29 | | Eric Allender,
Richard Beigel,
Ulrich Hertrampf,
Steven Homer:
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.
Theor. Comput. Sci. 115(2): 225-241 (1993) |
| 1992 |
|---|
| 28 | | Richard Beigel,
Jun Tarui,
Seinosuke Toda:
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate.
ISAAC 1992: 420-429 |
| 27 | | Richard Beigel,
Martin Kummer,
Frank Stephan:
Quantifying the Amount of Verboseness.
LFCS 1992: 21-32 |
| 26 | | Richard Beigel:
When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One
STOC 1992: 450-454 |
| 25 | | David A. Mix Barrington,
Richard Beigel,
Steven Rudich:
Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract)
STOC 1992: 455-461 |
| 24 | | Richard Beigel:
Perceptrons, PP, and the Polynomial Hierarchy.
Structure in Complexity Theory Conference 1992: 14-19 |
| 23 | | Richard Beigel,
Joan Feigenbaum:
On Being Incoherent Without Being Very Hard.
Computational Complexity 2: 1-17 (1992) |
| 22 | | Richard Beigel,
John Gill:
Counting Classes: Thresholds, Parity, Mods, and Fewness.
Theor. Comput. Sci. 103(1): 3-23 (1992) |
| 1991 |
|---|
| 21 | | Richard Beigel,
Mihir Bellare,
Joan Feigenbaum,
Shafi Goldwasser:
Languages that Are Easier than their Proofs
FOCS 1991: 19-28 |
| 20 | | Richard Beigel,
Jun Tarui:
On ACC
FOCS 1991: 783-792 |
| 19 | | Richard Beigel,
Nick Reingold,
Daniel A. Spielman:
PP Is Closed Under Intersection (Extended Abstract)
STOC 1991: 1-9 |
| 18 | | James Aspnes,
Richard Beigel,
Merrick L. Furst,
Steven Rudich:
The Expressive Power of Voting Polynomials
STOC 1991: 402-409 |
| 17 | | Richard Beigel,
Nick Reingold,
Daniel A. Spielman:
The Perceptron Strikes Back.
Structure in Complexity Theory Conference 1991: 286-291 |
| 16 | EE | Richard Beigel,
William I. Gasarch:
The Mapmaker's dilemma.
Discrete Applied Mathematics 34(1-3): 37-48 (1991) |
| 15 | | Richard Beigel,
Lane A. Hemachandra,
Gerd Wechsung:
Probabilistic Polynomial Time is Closed under Parity Reductions.
Inf. Process. Lett. 37(2): 91-94 (1991) |
| 14 | | Richard Beigel:
Relativized Counting Classes: Relations among Thresholds, Parity, and Mods.
J. Comput. Syst. Sci. 42(1): 76-96 (1991) |
| 13 | | Richard Beigel:
Bounded Queries to SAT and the Boolean Hierarchy.
Theor. Comput. Sci. 84(2): 199-223 (1991) |
| 1990 |
|---|
| 12 | | Eric Allender,
Richard Beigel,
Ulrich Hertrampf,
Steven Homer:
A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.
STACS 1990: 1-11 |
| 11 | | Richard Beigel,
John Gill,
Ulrich Hertrampf:
Counting Classes: Thresholds, Parity, Mods, and Fewness.
STACS 1990: 49-57 |
| 10 | | Amihood Amir,
Richard Beigel,
William I. Gasarch:
Some Connections Between Bounded Query Classes and Non-Uniform Complexity.
Structure in Complexity Theory Conference 1990: 232-243 |
| 9 | | Richard Beigel,
John Gill:
Sorting n Objects with a K-Sorter.
IEEE Trans. Computers 39(5): 714-716 (1990) |
| 8 | | Richard Beigel:
Unbounded Searching Slgorithms.
SIAM J. Comput. 19(3): 522-537 (1990) |
| 7 | | Richard Beigel:
Bi-Immunity Results for Cheatable Sets.
Theor. Comput. Sci. 73(3): 249-263 (1990) |
| 1989 |
|---|
| 6 | EE | Richard Beigel,
S. Rao Kosaraju,
Gregory F. Sullivan:
Locating Faults in a Constant Number of Parallel Testing Rounds.
SPAA 1989: 189-198 |
| 5 | | Richard Beigel:
On the Relativized Power of Additional Accepting Paths.
Structure in Complexity Theory Conference 1989: 216-224 |
| 4 | | Richard Beigel,
Lane A. Hemachandra,
Gerd Wechsung:
On the Power of Probabilistic Polynomial Time: PNP[log] subseteq PP.
Structure in Complexity Theory Conference 1989: 225-227 |
| 3 | | Richard Beigel,
William I. Gasarch,
James C. Owings:
Nondeterministic Bounded Query Reducibilities.
Ann. Pure Appl. Logic 41(2): 107-118 (1989) |
| 2 | | Richard Beigel,
William I. Gasarch:
On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.
Ann. Pure Appl. Logic 45(1): 1-38 (1989) |
| 1 | | Richard Beigel,
William I. Gasarch:
On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case.
Ann. Pure Appl. Logic 45(3): 227-246 (1989) |
