Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Richard Beigel:

TR11-028 | 24th February 2011
Richard Beigel, Bin Fu

A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

The bin packing problem is to find the minimum
number of bins of size one to pack a list of items with sizes
$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects
a random element from the input list each time, we develop a
randomized $O({n(\log n)(\log\log n)\over ... more >>>

TR04-015 | 24th February 2004
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

Enumerations of the Kolmogorov Function

A recursive enumerator for a function $h$ is an algorithm $f$ which
enumerates for an input $x$ finitely many elements including $h(x)$.
$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$
is among the first $k(n)$ elements enumerated by $f$.
If there is a $k(n)$-enumerator for ... more >>>

TR03-087 | 10th December 2003
Richard Beigel, Lance Fortnow, William Gasarch

A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

We show that any 1-round 2-server Private Information
Retrieval Protocol where the answers are 1-bit long must ask questions
that are at least $n-2$ bits long, which is nearly equal to the known
$n-1$ upper bound. This improves upon the approximately $0.25n$ lower
bound of Kerenidis and de Wolf while ... more >>>

TR00-024 | 16th May 2000
Amihood Amir, Richard Beigel, William Gasarch

Some Connections between Bounded Query Classes and Non-Uniform Complexity

Let A(x) be the characteristic function of A. Consider the function
F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be
computed with fewer than k queries to some set X, then A can be
computed by polynomial size circuits. A generalization of this result
has applications to bounded query ... more >>>

TR98-026 | 5th May 1998
Richard Beigel

Gaps in Bounded Query Hierarchies

Prior results show that most bounded query hierarchies cannot
contain finite gaps. For example, it is known that
P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>
and for all sets <i>A</i>
<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>
<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = ... more >>>

TR97-002 | 28th January 1997
Richard Beigel, Alexis Maciel

Upper and Lower Bounds for Some Depth-3 Circuit Classes

We investigate the complexity of depth-3 threshold circuits
with majority gates at the output, possibly negated AND
gates at level two, and MODm gates at level one. We show
that the fan-in of the AND gates can be reduced to O(log n)
in the case where ... more >>>

TR96-051 | 1st October 1996
Richard Beigel, William Gasarch, Ming Li, Louxin Zhang

Addition in $\log_2{n}$ + O(1)$ Steps on Average: A Simple Analysis

We demonstrate the use of Kolmogorov complexity in average case
analysis of algorithms through a classical example: adding two $n$-bit
numbers in $\ceiling{\log_2{n}}+2$ steps on average. We simplify the
analysis of Burks, Goldstine, and von Neumann in 1946 and
(in more complete forms) of Briley and of Schay.

more >>>

TR96-001 | 10th January 1996
Manindra Agrawal, Richard Beigel, Thomas Thierauf

Modulo Information from Nonadaptive Queries to NP

The classes of languages accepted by nondeterministic polynomial-time
Turing machines (NP machines, in short) that have restricted access to
an NP oracle --- the machines can ask k queries to the NP oracle and
the answer they receive is the number of queries ... more >>>

TR95-037 | 2nd July 1995
Richard Beigel, Howard Straubing

The Power of Local Self-Reductions

Identify a string x over {0,1} with the positive integer
whose binary representation is 1x. We say that a self-reduction is
k-local if on input x all queries belong to {x-1,...,x-k}. We show
that all k-locally self-reducible sets belong to PSPACE. However, the
power of k-local self-reductions changes drastically between ... more >>>

TR95-036 | 5th July 1995
Richard Beigel, William Gasarch, Efim Kinber

Frequency Computation and Bounded Queries

For a set A and a number n let F_n^A(x_1,...,x_n) =
A(x_1)\cdots A(x_n). We study how hard it is to approximate this
function in terms of the number of queries required. For a general
set A we have exact bounds that depend on functions from coding
theory. These are applied ... more >>>

TR95-035 | 30th June 1995
Richard Beigel

Closure Properties of GapP and #P

We classify the univariate functions that are relativizable
closure properties of GapP, solving a problem posed by Hertrampf,
Vollmer, and Wagner (Structures '95). We also give a simple proof of
their classification of univariate functions that are relativizable
closure properties of #P.

more >>>

TR95-033 | 29th June 1995
Richard Beigel, David Eppstein

3-Coloring in time O(1.3446^n): a no-MIS algorithm

We consider worst case time bounds for NP-complete problems
including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.
Our algorithms are based on a common generalization of these problems,
called symbol-system satisfiability or, briefly, SSS [R. Floyd &
R. Beigel, The Language of Machines]. 3-SAT is equivalent to
(2,3)-SSS while the other problems ... more >>>

ISSN 1433-8092 | Imprint