Richard Beigel

Publication Activity (10 Years)

Years Active: 1987-2016
Publications (10 Years): 1

Top Venues

CoRR

MSCC@MobiHoc

Theor. Comput. Sci.

FAW-AAIM

Publications

Richard Beigel, William I. Gasarch
On the sizes of DPDAs, PDAs, LBAs. Theor. Comput. Sci. 638 (2016)
Richard Beigel, William I. Gasarch
On the Sizes of DPDAs, PDAs, LBAs. CoRR (2015)
Richard Beigel, Jie Wu, Huanyang Zheng
On optimal scheduling of multiple mobile chargers in wireless sensor networks. MSCC@MobiHoc (2014)
Richard Beigel, Bin Fu
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. FAW-AAIM (2012)
Richard Beigel, Bin Fu
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. Electron. Colloquium Comput. Complex. 18 (2011)
Richard Beigel, Bin Fu
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing CoRR (2010)
Richard Beigel, Lance Fortnow, Frank Stephan
Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36 (3) (2006)
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. 71 (2) (2006)
Richard Beigel, William I. Gasarch, James Glenn
: Improved Bounds and New Problems. MFCS (2006)
Richard Beigel, Lance Fortnow, William I. Gasarch
A tight lower bound for restricted pir protocols. Comput. Complex. 15 (1) (2006)
Richard Beigel, David Eppstein
). J. Algorithms 54 (2) (2005)
Vilhelm Dahllöf, Peter Jonsson, Richard Beigel
Algorithms for four variants of the exact satisfiability problem. Theor. Comput. Sci. 320 (2-3) (2004)
Bin Fu, Richard Beigel
Diagnosis in the Presence of Intermittent Faults. ISAAC (2004)
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 Electron. Colloquium Comput. Complex. (015) (2004)
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
Learning a Hidden Matching. SIAM J. Comput. 33 (2) (2004)
Richard Beigel, Lance Fortnow, Frank Stephan
Infinitely-Often Autoreducible Sets. ISAAC (2003)
Richard Beigel, Lance Fortnow
Are Cook and Karp Ever the Same? Computational Complexity Conference (2003)
Amihood Amir, Richard Beigel, William I. Gasarch
Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186 (1) (2003)
Richard Beigel, Lance Fortnow, William I. Gasarch
A Nearly Tight Bound for Private Information Retrieval Protocols Electron. Colloquium Comput. Complex. (087) (2003)
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) (2002)
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
Learning a Hidden Matching. FOCS (2002)
Richard Beigel, Richard Chang
Commutative Queries. Inf. Comput. 166 (1) (2001)
Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow
An optimal procedure for gap closing in whole genome shotgun sequencing. RECOMB (2001)
Noga Alon, Richard Beigel
. Computational Complexity Conference (2001)
Richard Beigel, Bin Fu
Circuits over PP and PL. J. Comput. Syst. Sci. 60 (2) (2000)
Richard Beigel, David Eppstein
3-Coloring in Time O(1.3289^n) CoRR (2000)
Amihood Amir, Richard Beigel, William I. Gasarch
Some Connections between Bounded Query Classes and Non-Uniform Complexity Electron. Colloquium Comput. Complex. 7 (24) (2000)
Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy H. McNicholl, Frank Stephan
. J. Symb. Log. 65 (1) (2000)
Vikraman Arvind, Richard Beigel, Antoni Lozano
The Complexity of Modular Graph Automorphism. SIAM J. Comput. 30 (4) (2000)
Richard Beigel, Bin Fu
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. Algorithmica 25 (2-3) (1999)
Richard Beigel
Gaps in Bounded Query Hierarchies. Computational Complexity Conference (1999)
Richard Beigel, Anna Bernasconi
A Note on the Polynomial Representation of Boolean Functions over GF(2). Int. J. Found. Comput. Sci. 10 (4) (1999)
Richard Beigel
Finding Maximum Independent Sets in Sparse and General Graphs. SODA (1999)
Bin Fu, Richard Beigel
A Comparison of Resource-Bounded Molecular Computation Models. Algorithmica 24 (2) (1999)
Richard Beigel, Alexis Maciel
Circuit Lower Bounds Collapse Relativized Complexity Classes. Computational Complexity Conference (1999)
Vikraman Arvind, Richard Beigel, Antoni Lozano
The Complexity of Modular Graph Automorphism. STACS (1998)
Richard Beigel, Harry Buhrman, Lance Fortnow
NP Might Not Be As Easy As Detecting Unique Solutions. STOC (1998)
Richard Beigel
Gaps in Bounded Query Hierarchies Electron. Colloquium Comput. Complex. 5 (26) (1998)
Richard Beigel, Judy Goldsmith
Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. 27 (5) (1998)
Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang
n + O(1) Steps on Average: A Simple Analysis. Theor. Comput. Sci. 191 (1-2) (1998)
Richard Beigel, Egemen Tanin
The Geometry of Browsing. LATIN (1998)
Richard Beigel, Bin Fu
Solving Intractable Problems with DNA Computing. Computational Complexity Conference (1998)
Richard Beigel, Tirza Hirst
One Help Bit Doesn't Help. STOC (1998)
Egemen Tanin, Richard Beigel, Ben Shneiderman
Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. INFOVIS (1997)
Richard Beigel, Richard Chang
Commutative Queries. ISTCS (1997)
Richard Beigel, Bin Fu
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. ICALP (1997)
Richard Beigel, Alexis Maciel
Upper and Lower Bounds for Some Depth-3 Circuit Classes. Computational Complexity Conference (1997)
Bin Fu, Richard Beigel
A Comparison of Resource-Bounded Molecular Computation Models. ISTCS (1997)
Richard Beigel
Closure Properties of GapP and #P. ISTCS (1997)
Bin Fu, Richard Beigel
On molecular approximation algorithms for NP optimization problem. DNA Based Computers (1997)
Richard Beigel, Alexis Maciel
Upper and Lower Bounds for Some Depth-3 Circuit Classes Electron. Colloquium Comput. Complex. 4 (2) (1997)
Richard Beigel, Bin Fu
Circuits Over PP and PL. Computational Complexity Conference (1997)
Richard Beigel, Alexis Maciel
Upper and Lower Bounds for Some Depth-3 Circuit Classes. Comput. Complex. 6 (3) (1997)
Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan
On the Query Complexity of Sets. MFCS (1996)
Manindra Agrawal, Richard Beigel, Thomas Thierauf
Modulo Information from Nonadaptive Queries to NP Electron. Colloquium Comput. Complex. 3 (1) (1996)
Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang
n + O(1) Steps on Average: A Simple Analysis Electron. Colloquium Comput. Complex. 3 (51) (1996)
Manindra Agrawal, Richard Beigel, Thomas Thierauf
Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS (1996)
Egemen Tanin, Richard Beigel, Ben Shneiderman
Incremental data Structures and Algorithms for Dynamic Query Interfaces. SIGMOD Rec. 25 (4) (1996)
Richard Beigel, William I. Gasarch, Efim B. Kinber
Frequency Computation and Bounded Queries. Theor. Comput. Sci. 163 (1&2) (1996)
Richard Beigel, David Eppstein
): A no-MIS Algorithm Electron. Colloquium Comput. Complex. 2 (33) (1995)
Richard Beigel
Closure Properties of GapP and #P Electron. Colloquium Comput. Complex. 2 (35) (1995)
Richard Beigel, William I. Gasarch, Efim B. Kinber
Frequency Computation and Bounded Queries Electron. Colloquium Comput. Complex. 2 (36) (1995)
Richard Beigel, Howard Straubing
The Power of Local Self-Reductions Electron. Colloquium Comput. Complex. 2 (37) (1995)
Richard Beigel, Howard Straubing
The Power of Local Self-Reductions. Computational Complexity Conference (1995)
Richard Beigel, Martin Kummer, Frank Stephan
Quantifying the Amount of Verboseness Inf. Comput. 118 (1) (1995)
Richard Beigel, William Hurwood, Nabil Kahalé
Fault Diagnosis in a Flash. FOCS (1995)
Richard Beigel, Nick Reingold, Daniel A. Spielman
PP Is Closed under Intersection. J. Comput. Syst. Sci. 50 (2) (1995)
Richard Beigel, William I. Gasarch, Efim B. Kinber
Frequency Computation and Bounded Queries. Computational Complexity Conference (1995)
Richard Beigel, David Eppstein
): A No-MIS Algorithm. FOCS (1995)
Richard Beigel, Martin Kummer, Frank Stephan
Approximable Sets Inf. Comput. 120 (2) (1995)
Ming Gu, Martin Farach, Richard Beigel
An Efficient Algorithm for Dynamic Text Indexing. SODA (1994)
Richard Beigel, William Hurwood, Nabil Kahalé
Fault Diagnosis in a Flash Electron. Colloquium Comput. Complex. 1 (11) (1994)
David A. Mix Barrington, Richard Beigel, Steven Rudich
Representing Boolean Functions as Polynomials Modulo Composite Numbers. Comput. Complex. 4 (1994)
Richard Beigel
Perceptrons, PP, and the Polynomial Hierarchy. Comput. Complex. 4 (1994)
Richard Beigel
) Majority Gates Are Equivalent to One. Comput. Complex. 4 (1994)
Richard Beigel, Martin Kummer, Frank Stephan
Approximable Sets. Computational Complexity Conference (1994)
James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich
The Expressive Power of Voting Polynomials. Comb. 14 (2) (1994)
Richard Beigel, Judy Goldsmith
Downward separation fails catastrophically for limited nondeterminism classes. Computational Complexity Conference (1994)
Richard Beigel, Jun Tarui
On ACC. Comput. Complex. 4 (1994)
Richard Beigel, Grigorii Margulis, Daniel A. Spielman
Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds. SPAA (1993)
Richard Beigel
The Polynomial Method in Circuit Complexity. Computational Complexity Conference (1993)
Sreerama K. Murthy, Simon Kasif, Steven Salzberg, Richard Beigel
OC1: A Randomized Induction of Oblique Decision Trees. AAAI (1993)
Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115 (2) (1993)
Richard Beigel, William I. Gasarch, John Gill, James C. Owings
Terse, Superterse, and Verbose Sets Inf. Comput. 103 (1) (1993)
Richard Beigel, Richard Chang, Mitsunori Ogiwara
A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies. Math. Syst. Theory 26 (3) (1993)
Richard Beigel
Perceptrons, PP, and the Polynomial Hierarchy. Computational Complexity Conference (1992)
David A. Mix Barrington, Richard Beigel, Steven Rudich
Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) STOC (1992)
Richard Beigel, Martin Kummer, Frank Stephan
Quantifying the Amount of Verboseness. LFCS (1992)
Richard Beigel, John Gill
Counting Classes: Thresholds, Parity, Mods, and Fewness. Theor. Comput. Sci. 103 (1) (1992)
Richard Beigel, Jun Tarui, Seinosuke Toda
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. ISAAC (1992)
Richard Beigel
When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One STOC (1992)
Richard Beigel, Joan Feigenbaum
On Being Incoherent Without Being Very Hard. Comput. Complex. 2 (1992)
Richard Beigel, Nick Reingold, Daniel A. Spielman
PP Is Closed Under Intersection (Extended Abstract) STOC (1991)
Richard Beigel, Clyde P. Kruskal
Processor networks and interconnection networks without long wires (extended abstract). SIGARCH Comput. Archit. News 19 (1) (1991)
Richard Beigel, Nick Reingold, Daniel A. Spielman
The Perceptron Strikes Back. Computational Complexity Conference (1991)
Richard Beigel, William I. Gasarch
The Mapmaker's dilemma. Discret. Appl. Math. 34 (1-3) (1991)
Richard Beigel, Jun Tarui
On ACC FOCS (1991)
Richard Beigel
Bounded Queries to SAT and the Boolean Hierarchy. Theor. Comput. Sci. 84 (2) (1991)
James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich
The Expressive Power of Voting Polynomials STOC (1991)
Richard Beigel, Lane A. Hemachandra, Gerd Wechsung
Probabilistic Polynomial Time is Closed under Parity Reductions. Inf. Process. Lett. 37 (2) (1991)

Richard Beigel.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Richard Beigel