| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Richard Beigel, Bin Fu |
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing.  |
FAW-AAIM  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Bin Fu |
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Bin Fu |
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet |
Enumerations of the Kolmogorov function. |
J. Symb. Log. |
2006 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Lance Fortnow, William I. Gasarch |
A tight lower bound for restricted pir protocols. |
Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification |
| 1 | Richard Beigel, Lance Fortnow, Frank Stephan |
Infinitely-Often Autoreducible Sets. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, James Glenn |
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. |
MFCS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, David Eppstein |
3-coloring in time O(1.3289n). |
J. Algorithms |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | 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) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Vilhelm Dahllöf, Peter Jonsson, Richard Beigel |
Algorithms for four variants of the exact satisfiability problem. |
Theor. Comput. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov |
Learning a Hidden Matching. |
SIAM J. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Bin Fu, Richard Beigel |
Diagnosis in the Presence of Intermittent Faults. |
ISAAC |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Lance Fortnow, William I. Gasarch |
A Nearly Tight Bound for Private Information Retrieval Protocols |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Amihood Amir, Richard Beigel, William I. Gasarch |
Some connections between bounded query classes and non-uniform complexity. |
Inf. Comput. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Lance Fortnow, Frank Stephan |
Infinitely-Often Autoreducible Sets. |
ISAAC |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Lance Fortnow |
Are Cook and Karp Ever the Same? |
IEEE Conference on Computational Complexity |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov |
Learning a Hidden Matching. |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Richard Chang |
Commutative Queries. |
Inf. Comput. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow |
An optimal procedure for gap closing in whole genome shotgun sequencing. |
RECOMB |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Richard Beigel |
Lower Bounds for Approximations by Low Degree Polynomials Over Zm. (PDF / PS) |
IEEE Conference on Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Amihood Amir, Richard Beigel, William I. Gasarch |
Some Connections between Bounded Query Classes and Non-Uniform Complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2000 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl, Frank Stephan |
The Comlexity of OddAn. |
J. Symb. Log. |
2000 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, David Eppstein |
3-Coloring in Time O(1.3289^n) |
CoRR |
2000 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Bin Fu |
Circuits over PP and PL. |
J. Comput. Syst. Sci. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Vikraman Arvind, Richard Beigel, Antoni Lozano |
The Complexity of Modular Graph Automorphism. |
SIAM J. Comput. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Anna Bernasconi |
A Note on the Polynomial Representation of Boolean Functions over GF(2). |
Int. J. Found. Comput. Sci. |
1999 |
DBLP BibTeX RDF |
|
| 1 | Bin Fu, Richard Beigel |
A Comparison of Resource-Bounded Molecular Computation Models. |
Algorithmica |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Bin Fu |
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. |
Algorithmica |
1999 |
DBLP DOI BibTeX RDF |
Nondeterminism, Molecular computing, Volume |
| 1 | Richard Beigel |
Finding Maximum Independent Sets in Sparse and General Graphs. |
SODA |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
Gaps in Bounded Query Hierarchies. (PDF / PS) |
IEEE Conference on Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
complexity, separation, collapse, bounded queries |
| 1 | Richard Beigel, Alexis Maciel |
Circuit Lower Bounds Collapse Relativized Complexity Classes. (PDF / PS) |
IEEE Conference on Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
relativized computation, Booleand circuits, oracles, complexity theory |
| 1 | Richard Beigel |
Gaps in Bounded Query Hierarchies |
Electronic Colloquium on Computational Complexity (ECCC) |
1998 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang |
Addition in log2n + O(1) Steps on Average: A Simple Analysis. |
Theor. Comput. Sci. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Judy Goldsmith |
Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. |
SIAM J. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Egemen Tanin |
The Geometry of Browsing. |
LATIN |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Vikraman Arvind, Richard Beigel, Antoni Lozano |
The Complexity of Modular Graph Automorphism. |
STACS |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Bin Fu |
Solving Intractable Problems with DNA Computing. (PDF / PS) |
IEEE Conference on Computational Complexity |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Tirza Hirst |
One Help Bit Doesn't Help. |
STOC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Harry Buhrman, Lance Fortnow |
NP Might Not Be As Easy As Detecting Unique Solutions. |
STOC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Alexis Maciel |
Upper and Lower Bounds for Some Depth-3 Circuit Classes |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Alexis Maciel |
Upper and Lower Bounds for Some Depth-3 Circuit Classes. |
Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Bin Fu |
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. |
ICALP |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Egemen Tanin, Richard Beigel, Ben Shneiderman |
Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. |
INFOVIS |
1997 |
DBLP DOI BibTeX RDF |
Direct Manipulation and Dynamic Query, Algorithm, User Interface, Information Visualization, Database, Data Structure |
| 1 | Richard Beigel, Richard Chang |
Commutative Queries. (PDF / PS) |
ISTCS |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
Closure Properties of GapP and #P. (PDF / PS) |
ISTCS |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Bin Fu, Richard Beigel |
A Comparison of Resource-Bounded Molecular Computation Models. (PDF / PS) |
ISTCS |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Alexis Maciel |
Upper and Lower Bounds for Some Depth-3 Circuit Classes. (PDF / PS) |
IEEE Conference on Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
constant depth, majority gate, MOD gate, inner product mod 2, threshold circuit |
| 1 | Richard Beigel, Bin Fu |
Circuits Over PP and PL. (PDF / PS) |
IEEE Conference on Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
reduction, oracle, circuit, closure, PL, Boolean formula, AC, NC, PP |
| 1 | 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) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Manindra Agrawal, Richard Beigel, Thomas Thierauf |
Modulo Information from Nonadaptive Queries to NP |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, Efim B. Kinber |
Frequency Computation and Bounded Queries. |
Theor. Comput. Sci. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Egemen Tanin, Richard Beigel, Ben Shneiderman |
Incremental data Structures and Algorithms for Dynamic Query Interfaces. |
SIGMOD Record |
1996 |
DBLP DOI BibTeX RDF |
algorithm, user interface, information visualization, database, data structure, direct manipulation, dynamic query |
| 1 | Robert W. Floyd, Richard Beigel |
Die Sprache der Maschinen. |
|
1996 |
RDF |
|
| 1 | Richard Beigel, William I. Gasarch, Martin Kummer, Timothy McNicholl, Frank Stephan |
On the Query Complexity of Sets. |
MFCS |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Richard Beigel, Thomas Thierauf |
Pinpointing Computation with Modular Queries in the Boolean Hierarchy. |
FSTTCS |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, David Eppstein |
3-Coloring in time O(1.3446n): A no-MIS Algorithm |
Electronic Colloquium on Computational Complexity (ECCC) |
1995 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, Efim B. Kinber |
Frequency Computation and Bounded Queries |
Electronic Colloquium on Computational Complexity (ECCC) |
1995 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Howard Straubing |
The Power of Local Self-Reductions |
Electronic Colloquium on Computational Complexity (ECCC) |
1995 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel |
Closure Properties of GapP and #P |
Electronic Colloquium on Computational Complexity (ECCC) |
1995 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Martin Kummer, Frank Stephan |
Quantifying the Amount of Verboseness |
Inf. Comput. |
1995 |
RDF |
|
| 1 | Richard Beigel, Martin Kummer, Frank Stephan |
Approximable Sets |
Inf. Comput. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Nick Reingold, Daniel A. Spielman |
PP Is Closed under Intersection. |
J. Comput. Syst. Sci. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, David Eppstein |
3-Coloring in Time O(1.3446n): A No-MIS Algorithm. |
FOCS |
1995 |
DBLP DOI BibTeX RDF |
duality (mathematics), 3-coloring, worst case time bounds, 3-edge-coloring, 3-list-coloring, common generalization, symbol-system satisfiability, duality transformation, computational complexity, computability, decidability, NP-complete problems, graph colouring, time bounds, 3-SAT |
| 1 | Richard Beigel, William Hurwood, Nabil Kahale |
Fault Diagnosis in a Flash. |
FOCS |
1995 |
DBLP DOI BibTeX RDF |
parallel testing rounds, deterministic preprocessing, randomised preprocessing, parallel algorithms, reliability, fault diagnosis, fault diagnosis, fault tolerant computing, built-in self test, computer testing, faulty processors |
| 1 | Richard Beigel, Howard Straubing |
The Power of Local Self-Reductions. |
Structure in Complexity Theory Conference |
1995 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, Efim B. Kinber |
Frequency Computation and Bounded Queries. |
Structure in Complexity Theory Conference |
1995 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, William Hurwood, Nabil Kahale |
Fault Diagnosis in a Flash |
Electronic Colloquium on Computational Complexity (ECCC) |
1994 |
DBLP BibTeX RDF |
|
| 1 | James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich |
The Expressive Power of Voting Polynomials. |
Combinatorica |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | David A. Mix Barrington, Richard Beigel, Steven Rudich |
Representing Boolean Functions as Polynomials Modulo Composite Numbers. |
Computational Complexity |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
Perceptrons, PP, and the Polynomial Hierarchy. |
Computational Complexity |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
When do Extra Majority Gates Help? Polylog(N) Majority Gates Are Equivalent to One. |
Computational Complexity |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Jun Tarui |
On ACC. |
Computational Complexity |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Ming Gu, Martin Farach, Richard Beigel |
An Efficient Algorithm for Dynamic Text Indexing. |
SODA |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Judy Goldsmith |
Downward separation fails catastrophically for limited nondeterminism classes. |
Structure in Complexity Theory Conference |
1994 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Martin Kummer, Frank Stephan |
Approximable Sets. |
Structure in Complexity Theory Conference |
1994 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer |
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. |
Theor. Comput. Sci. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, John Gill, James C. Owings |
Terse, Superterse, and Verbose Sets |
Inf. Comput. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Richard Chang, Mitsunori Ogiwara |
A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies. |
Mathematical Systems Theory |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Grigorii Margulis, Daniel A. Spielman |
Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds. |
SPAA |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
The Polynomial Method in Circuit Complexity. |
Structure in Complexity Theory Conference |
1993 |
DBLP BibTeX RDF |
|
| 1 | Sreerama K. Murthy, Simon Kasif, Steven Salzberg, Richard Beigel |
OC1: A Randomized Induction of Oblique Decision Trees. |
AAAI |
1993 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, John Gill |
Counting Classes: Thresholds, Parity, Mods, and Fewness. |
Theor. Comput. Sci. |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Joan Feigenbaum |
On Being Incoherent Without Being Very Hard. |
Computational Complexity |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Martin Kummer, Frank Stephan |
Quantifying the Amount of Verboseness. |
LFCS |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Jun Tarui, Seinosuke Toda |
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. |
ISAAC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
Perceptrons, PP, and the Polynomial Hierarchy. |
Structure in Complexity Theory Conference |
1992 |
DBLP BibTeX RDF |
|
| 1 | David A. Mix Barrington, Richard Beigel, Steven Rudich |
Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) |
STOC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One |
STOC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Lane A. Hemachandra, Gerd Wechsung |
Probabilistic Polynomial Time is Closed under Parity Reductions. |
Inf. Process. Lett. |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
Bounded Queries to SAT and the Boolean Hierarchy. |
Theor. Comput. Sci. |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch |
The Mapmaker's dilemma. |
Discrete Applied Mathematics |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
Relativized Counting Classes: Relations among Thresholds, Parity, and Mods. |
J. Comput. Syst. Sci. |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser |
Languages that Are Easier than their Proofs |
FOCS |
1991 |
DBLP DOI BibTeX RDF |
nonrandom self-reducible sets, triple-exponential time, incoherent sets, formal languages, membership, NP, DSPACE |
| 1 | Richard Beigel, Jun Tarui |
On ACC |
FOCS |
1991 |
DBLP DOI BibTeX RDF |
modulus-amplifying polynomials, ACC, depth-2 probabilistic circuits, symmetric gate, depth-2 deterministic circuits, language, root, fan-in, AND gates, leaves |
| 1 | Richard Beigel, Nick Reingold, Daniel A. Spielman |
The Perceptron Strikes Back. |
Structure in Complexity Theory Conference |
1991 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Nick Reingold, Daniel A. Spielman |
PP Is Closed Under Intersection (Extended Abstract) |
STOC |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich |
The Expressive Power of Voting Polynomials |
STOC |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
Bi-Immunity Results for Cheatable Sets. |
Theor. Comput. Sci. |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, John Gill |
Sorting n Objects with a K-Sorter. |
IEEE Trans. Computers |
1990 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")