Richard Beigel

According to our database, Richard Beigel authored at least 90 papers between 1987 and 2016.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2016

On the sizes of DPDAs, PDAs, LBAs.

Richard Beigel, William I. Gasarch

Theor. Comput. Sci., 2016

2014

On optimal scheduling of multiple mobile chargers in wireless sensor networks.

Richard Beigel, Jie Wu, Huanyang Zheng

Proceedings of the first international workshop on Mobile sensing, 2014

2011

A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing.

Richard Beigel, Bin Fu

Electron. Colloquium Comput. Complex., 2011

2006

Infinitely-Often Autoreducible Sets.

Richard Beigel, Lance Fortnow, Frank Stephan

SIAM J. Comput., 2006

Enumerations of the Kolmogorov function.

Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

J. Symb. Log., 2006

A tight lower bound for restricted pir protocols.

Richard Beigel, Lance Fortnow, William I. Gasarch

Comput. Complex., 2006

The Multiparty Communication Complexity of Exact-<i>T</i>: Improved Bounds and New Problems.

Richard Beigel, William I. Gasarch, James Glenn

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

2005

3-coloring in time O(1.3289ⁿ).

Richard Beigel, David Eppstein

J. Algorithms, 2005

2004

Algorithms for four variants of the exact satisfiability problem.

Vilhelm Dahllöf, Peter Jonsson, Richard Beigel

Theor. Comput. Sci., 2004

Learning a Hidden Matching.

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov

SIAM J. Comput., 2004

Diagnosis in the Presence of Intermittent Faults.

Bin Fu, Richard Beigel

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003

A Nearly Tight Bound for Private Information Retrieval Protocols

Richard Beigel, Lance Fortnow, William I. Gasarch

Electron. Colloquium Comput. Complex., 2003

Are Cook and Karp Ever the Same?

Richard Beigel, Lance Fortnow

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph.

Richard Beigel, Lane A. Hemaspaandra, Harald Hempel, Jörg Vogel

Inf. Comput., 2002

2001

Commutative Queries.

Richard Beigel, Richard Chang

Inf. Comput., 2001

An optimal procedure for gap closing in whole genome shotgun sequencing.

Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow

Proceedings of the Fifth Annual International Conference on Computational Biology, 2001

Lower Bounds for Approximations by Low Degree Polynomials Over Z_m.

Noga Alon, Richard Beigel

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

The Complexity of Modular Graph Automorphism.

Vikraman Arvind, Richard Beigel, Antoni Lozano

SIAM J. Comput., 2000

The Comlexity of Odd^A_n.

Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy H. McNicholl, Frank Stephan

J. Symb. Log., 2000

Circuits over PP and PL.

Richard Beigel, Bin Fu

J. Comput. Syst. Sci., 2000

Some Connections between Bounded Query Classes and Non-Uniform Complexity

Amihood Amir, Richard Beigel, William I. Gasarch

Electron. Colloquium Comput. Complex., 2000

3-Coloring in Time O(1.3289^n)

Richard Beigel, David Eppstein

CoRR, 2000

1999

A Note on the Polynomial Representation of Boolean Functions over GF(2).

Richard Beigel, Anna Bernasconi

Int. J. Found. Comput. Sci., 1999

A Comparison of Resource-Bounded Molecular Computation Models.

Bin Fu, Richard Beigel

Algorithmica, 1999

Molecular Computing, Bounded Nondeterminism, and Efficient Recursion.

Richard Beigel, Bin Fu

Algorithmica, 1999

Finding Maximum Independent Sets in Sparse and General Graphs.

Richard Beigel

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Circuit Lower Bounds Collapse Relativized Complexity Classes.

Richard Beigel, Alexis Maciel

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Addition in log₂n + O(1) Steps on Average: A Simple Analysis.

Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang

Theor. Comput. Sci., 1998

Downward Separation Fails Catastrophically for Limited Nondeterminism Classes.

Richard Beigel, Judy Goldsmith

SIAM J. Comput., 1998

Gaps in Bounded Query Hierarchies

Richard Beigel

Electron. Colloquium Comput. Complex., 1998

One Help Bit Doesn't Help.

Richard Beigel, Tirza Hirst

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

NP Might Not Be As Easy As Detecting Unique Solutions.

Richard Beigel, Harry Buhrman, Lance Fortnow

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Geometry of Browsing.

Richard Beigel, Egemen Tanin

Proceedings of the LATIN '98: Theoretical Informatics, 1998

Solving Intractable Problems with DNA Computing.

Richard Beigel, Bin Fu

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Upper and Lower Bounds for Some Depth-3 Circuit Classes.

Richard Beigel, Alexis Maciel

Comput. Complex., 1997

Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces.

Egemen Tanin, Richard Beigel, Ben Shneiderman

Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis '97), 1997

On molecular approximation algorithms for NP optimization problem.

Bin Fu, Richard Beigel

Proceedings of the DNA Based Computers, 1997

1996

Frequency Computation and Bounded Queries.

Richard Beigel, William I. Gasarch, Efim B. Kinber

Theor. Comput. Sci., 1996

Incremental data Structures and Algorithms for Dynamic Query Interfaces.

Egemen Tanin, Richard Beigel, Ben Shneiderman

SIGMOD Rec., 1996

Modulo Information from Nonadaptive Queries to NP

Manindra Agrawal, Richard Beigel, Thomas Thierauf

Electron. Colloquium Comput. Complex., 1996

On the Query Complexity of Sets.

Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan

Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

Pinpointing Computation with Modular Queries in the Boolean Hierarchy.

Manindra Agrawal, Richard Beigel, Thomas Thierauf

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

Die Sprache der Maschinen.

Robert W. Floyd, Richard Beigel

Informatik Lehrbuch-Reihe, International Thomson, ISBN: 978-3-8266-0216-0, 1996

1995

Approximable Sets

Richard Beigel, Martin Kummer, Frank Stephan

Inf. Comput., August, 1995

Quantifying the Amount of Verboseness

Richard Beigel, Martin Kummer, Frank Stephan

Inf. Comput., April, 1995

PP Is Closed under Intersection.

Richard Beigel, Nick Reingold, Daniel A. Spielman

J. Comput. Syst. Sci., 1995

The Power of Local Self-Reductions

Richard Beigel, Howard Straubing

Electron. Colloquium Comput. Complex., 1995

Closure Properties of GapP and #P

Richard Beigel

Electron. Colloquium Comput. Complex., 1995

3-Coloring in time O(1.3446ⁿ): A no-MIS Algorithm

Richard Beigel, David Eppstein

Electron. Colloquium Comput. Complex., 1995

1994

Fault Diagnosis in a Flash

Richard Beigel, William Hurwood, Nabil Kahalé

Electron. Colloquium Comput. Complex., 1994

The Expressive Power of Voting Polynomials.

James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich

Comb., 1994

On ACC.

Richard Beigel, Jun Tarui

Comput. Complex., 1994

Perceptrons, PP, and the Polynomial Hierarchy.

Richard Beigel

Comput. Complex., 1994

When do Extra Majority Gates Help? Polylog(<i>N</i>) Majority Gates Are Equivalent to One.

Richard Beigel

Comput. Complex., 1994

Representing Boolean Functions as Polynomials Modulo Composite Numbers.

David A. Mix Barrington, Richard Beigel, Steven Rudich

Comput. Complex., 1994

An Efficient Algorithm for Dynamic Text Indexing.

Ming Gu, Martin Farach, Richard Beigel

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Terse, Superterse, and Verbose Sets

Richard Beigel, William I. Gasarch, John Gill, James C. Owings

Inf. Comput., March, 1993

Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Theor. Comput. Sci., 1993

A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies.

Richard Beigel, Richard Chang, Mitsunori Ogiwara

Math. Syst. Theory, 1993

Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds.

Richard Beigel, Grigorii Margulis, Daniel A. Spielman

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

The Polynomial Method in Circuit Complexity.

Richard Beigel

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

OC1: A Randomized Induction of Oblique Decision Trees.

Sreerama K. Murthy, Simon Kasif, Steven Salzberg, Richard Beigel

Proceedings of the 11th National Conference on Artificial Intelligence. Washington, 1993

1992

Counting Classes: Thresholds, Parity, Mods, and Fewness.

Richard Beigel, John Gill

Theor. Comput. Sci., 1992

On Being Incoherent Without Being Very Hard.

Richard Beigel, Joan Feigenbaum

Comput. Complex., 1992

When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One

Richard Beigel

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract)

David A. Mix Barrington, Richard Beigel, Steven Rudich

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On Probabilistic ACC Circuits with an Exact-Threshold Output Gate.

Richard Beigel, Jun Tarui, Seinosuke Toda

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

1991

Bounded Queries to SAT and the Boolean Hierarchy.

Richard Beigel

Theor. Comput. Sci., 1991

Processor networks and interconnection networks without long wires (extended abstract).

Richard Beigel, Clyde P. Kruskal

SIGARCH Comput. Archit. News, 1991

Relativized Counting Classes: Relations among Thresholds, Parity, and Mods.

Richard Beigel

J. Comput. Syst. Sci., 1991

Probabilistic Polynomial Time is Closed under Parity Reductions.

Richard Beigel, Lane A. Hemachandra, Gerd Wechsung

Inf. Process. Lett., 1991

The Mapmaker's dilemma.

Richard Beigel, William I. Gasarch

Discret. Appl. Math., 1991

PP Is Closed Under Intersection (Extended Abstract)

Richard Beigel, Nick Reingold, Daniel A. Spielman

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Languages that Are Easier than their Proofs

Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

The Perceptron Strikes Back.

Richard Beigel, Nick Reingold, Daniel A. Spielman

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Bi-Immunity Results for Cheatable Sets.

Richard Beigel

Theor. Comput. Sci., 1990

Sorting n Objects with a K-Sorter.

Richard Beigel, John Gill

IEEE Trans. Computers, 1990

Unbounded Searching Slgorithms.

Richard Beigel

SIAM J. Comput., 1990

Counting Classes: Thresholds, Parity, Mods, and Fewness.

Richard Beigel, John Gill, Ulrich Hertrampf

Proceedings of the STACS 90, 1990

A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Proceedings of the STACS 90, 1990

1989

Primitive recursion without implicit predecessor.

Michael J. Fischer, Robert P. Fischer, Richard Beigel

SIGACT News, 1989

Nondeterministic Bounded Query Reducibilities.

Richard Beigel, William I. Gasarch, James C. Owings

Ann. Pure Appl. Log., 1989

On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case.

Richard Beigel, William I. Gasarch

Ann. Pure Appl. Log., 1989

On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.

Richard Beigel, William I. Gasarch

Ann. Pure Appl. Log., 1989

Bounded query classes and the difference hierarchy.

Richard Beigel, William I. Gasarch, Louise Hay

Arch. Math. Log., 1989

Locating Faults in a Constant Number of Parallel Testing Rounds.

Richard Beigel, S. Rao Kosaraju, Gregory F. Sullivan

Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

On the Power of Probabilistic Polynomial Time: P^NP[log] subseteq PP.

Richard Beigel, Lane A. Hemachandra, Gerd Wechsung

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

On the Relativized Power of Additional Accepting Paths.

Richard Beigel

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1987

Query-limited reducibilities.

Richard Beigel

PhD thesis, 1987

A structural theorem that depends quantitatively on the complexity of SAT.

Richard Beigel

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987