Richard Beigel

According to our database1, Richard Beigel authored at least 89 papers between 1987 and 2016.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2016
On the sizes of DPDAs, PDAs, LBAs.
Theor. Comput. Sci., 2016

2014
On optimal scheduling of multiple mobile chargers in wireless sensor networks.
Proceedings of the first international workshop on Mobile sensing, 2014

2011
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing.
Electron. Colloquium Comput. Complex., 2011

2006
Infinitely-Often Autoreducible Sets.
SIAM J. Comput., 2006

Enumerations of the Kolmogorov function.
J. Symb. Log., 2006

A tight lower bound for restricted pir protocols.
Comput. Complex., 2006

The Multiparty Communication Complexity of Exact-<i>T</i>: Improved Bounds and New Problems.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

2005
3-coloring in time O(1.3289<sup>n</sup>).
J. Algorithms, 2005

2004
Algorithms for four variants of the exact satisfiability problem.
Theor. Comput. Sci., 2004

Learning a Hidden Matching.
SIAM J. Comput., 2004

Diagnosis in the Presence of Intermittent Faults.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003
A Nearly Tight Bound for Private Information Retrieval Protocols
Electron. Colloquium Comput. Complex., 2003

Are Cook and Karp Ever the Same?
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.
Inf. Comput., 2002

2001
Commutative Queries.
Inf. Comput., 2001

An optimal procedure for gap closing in whole genome shotgun sequencing.
Proceedings of the Fifth Annual International Conference on Computational Biology, 2001

Lower Bounds for Approximations by Low Degree Polynomials Over Z<sub>m</sub>.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
The Complexity of Modular Graph Automorphism.
SIAM J. Comput., 2000

The Comlexity of Odd<sup>A</sup><sub>n</sub>.
J. Symb. Log., 2000

Circuits over PP and PL.
J. Comput. Syst. Sci., 2000

Some Connections between Bounded Query Classes and Non-Uniform Complexity
Electron. Colloquium Comput. Complex., 2000

3-Coloring in Time O(1.3289^n)
CoRR, 2000

1999
A Note on the Polynomial Representation of Boolean Functions over GF(2).
Int. J. Found. Comput. Sci., 1999

A Comparison of Resource-Bounded Molecular Computation Models.
Algorithmica, 1999

Molecular Computing, Bounded Nondeterminism, and Efficient Recursion.
Algorithmica, 1999

Finding Maximum Independent Sets in Sparse and General Graphs.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Circuit Lower Bounds Collapse Relativized Complexity Classes.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Addition in log<sub>2</sub>n + O(1) Steps on Average: A Simple Analysis.
Theor. Comput. Sci., 1998

Downward Separation Fails Catastrophically for Limited Nondeterminism Classes.
SIAM J. Comput., 1998

Gaps in Bounded Query Hierarchies
Electron. Colloquium Comput. Complex., 1998

One Help Bit Doesn't Help.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

NP Might Not Be As Easy As Detecting Unique Solutions.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Geometry of Browsing.
Proceedings of the LATIN '98: Theoretical Informatics, 1998

Solving Intractable Problems with DNA Computing.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
Upper and Lower Bounds for Some Depth-3 Circuit Classes.
Comput. Complex., 1997

Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces.
Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis '97), 1997

On molecular approximation algorithms for NP optimization problem.
Proceedings of the DNA Based Computers, 1997

1996
Frequency Computation and Bounded Queries.
Theor. Comput. Sci., 1996

Incremental data Structures and Algorithms for Dynamic Query Interfaces.
SIGMOD Rec., 1996

Modulo Information from Nonadaptive Queries to NP
Electron. Colloquium Comput. Complex., 1996

On the Query Complexity of Sets.
Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

Pinpointing Computation with Modular Queries in the Boolean Hierarchy.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

Die Sprache der Maschinen.
Informatik Lehrbuch-Reihe, International Thomson, ISBN: 978-3-8266-0216-0, 1996

1995
Approximable Sets
Inf. Comput., August, 1995

Quantifying the Amount of Verboseness
Inf. Comput., April, 1995

PP Is Closed under Intersection.
J. Comput. Syst. Sci., 1995

The Power of Local Self-Reductions
Electron. Colloquium Comput. Complex., 1995

Closure Properties of GapP and #P
Electron. Colloquium Comput. Complex., 1995

3-Coloring in time O(1.3446<sup>n</sup>): A no-MIS Algorithm
Electron. Colloquium Comput. Complex., 1995

1994
Fault Diagnosis in a Flash
Electron. Colloquium Comput. Complex., 1994

The Expressive Power of Voting Polynomials.
Comb., 1994

On ACC.
Comput. Complex., 1994

Perceptrons, PP, and the Polynomial Hierarchy.
Comput. Complex., 1994

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

Representing Boolean Functions as Polynomials Modulo Composite Numbers.
Comput. Complex., 1994

An Efficient Algorithm for Dynamic Text Indexing.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
Terse, Superterse, and Verbose Sets
Inf. Comput., March, 1993

Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.
Theor. Comput. Sci., 1993

A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies.
Math. Syst. Theory, 1993

Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

The Polynomial Method in Circuit Complexity.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, 1993

OC1: A Randomized Induction of Oblique Decision Trees.
Proceedings of the 11th National Conference on Artificial Intelligence. Washington, 1993

1992
Counting Classes: Thresholds, Parity, Mods, and Fewness.
Theor. Comput. Sci., 1992

On Being Incoherent Without Being Very Hard.
Comput. Complex., 1992

When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On Probabilistic ACC Circuits with an Exact-Threshold Output Gate.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

1991
Bounded Queries to SAT and the Boolean Hierarchy.
Theor. Comput. Sci., 1991

Processor networks and interconnection networks without long wires (extended abstract).
SIGARCH Comput. Archit. News, 1991

Relativized Counting Classes: Relations among Thresholds, Parity, and Mods.
J. Comput. Syst. Sci., 1991

Probabilistic Polynomial Time is Closed under Parity Reductions.
Inf. Process. Lett., 1991

The Mapmaker's dilemma.
Discret. Appl. Math., 1991

PP Is Closed Under Intersection (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Languages that Are Easier than their Proofs
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

The Perceptron Strikes Back.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991

1990
Bi-Immunity Results for Cheatable Sets.
Theor. Comput. Sci., 1990

Sorting n Objects with a K-Sorter.
IEEE Trans. Computers, 1990

Unbounded Searching Slgorithms.
SIAM J. Comput., 1990

Counting Classes: Thresholds, Parity, Mods, and Fewness.
Proceedings of the STACS 90, 1990

A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.
Proceedings of the STACS 90, 1990

1989
Primitive recursion without implicit predecessor.
SIGACT News, 1989

Nondeterministic Bounded Query Reducibilities.
Ann. Pure Appl. Log., 1989

On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case.
Ann. Pure Appl. Log., 1989

On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.
Ann. Pure Appl. Log., 1989

Bounded query classes and the difference hierarchy.
Arch. Math. Log., 1989

Locating Faults in a Constant Number of Parallel Testing Rounds.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

On the Power of Probabilistic Polynomial Time: P<sup>NP[log]</sup> subseteq PP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

On the Relativized Power of Additional Accepting Paths.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1987
A structural theorem that depends quantitatively on the complexity of SAT.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987


  Loading...