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

__
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

__
TR03-087
| 10th December 2003
__

Richard Beigel, Lance Fortnow, William Gasarch#### A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

__
TR00-024
| 16th May 2000
__

Amihood Amir, Richard Beigel, William Gasarch#### Some Connections between Bounded Query Classes and Non-Uniform Complexity

__
TR98-026
| 5th May 1998
__

Richard Beigel#### Gaps in Bounded Query Hierarchies

__
TR97-002
| 28th January 1997
__

Richard Beigel, Alexis Maciel#### Upper and Lower Bounds for Some Depth-3 Circuit Classes

__
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

__
TR96-001
| 10th January 1996
__

Manindra Agrawal, Richard Beigel, Thomas Thierauf#### Modulo Information from Nonadaptive Queries to NP

__
TR95-037
| 2nd July 1995
__

Richard Beigel, Howard Straubing#### The Power of Local Self-Reductions

__
TR95-036
| 5th July 1995
__

Richard Beigel, William Gasarch, Efim Kinber#### Frequency Computation and Bounded Queries

__
TR95-035
| 30th June 1995
__

Richard Beigel#### Closure Properties of GapP and #P

__
TR95-033
| 29th June 1995
__

Richard Beigel, David Eppstein#### 3-Coloring in time O(1.3446^n): a no-MIS algorithm

Richard Beigel, Bin Fu

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 >>>

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

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 >>>

Richard Beigel, Lance Fortnow, William Gasarch

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 >>>

Amihood Amir, Richard Beigel, William Gasarch

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 >>>

Richard Beigel

<html>

Prior results show that most bounded query hierarchies cannot

contain finite gaps. For example, it is known that

<center>

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>

</center>

and for all sets <i>A</i>

<ul>

<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>

<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 >>>

Richard Beigel, Alexis Maciel

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 >>>

Richard Beigel, William Gasarch, Ming Li, Louxin Zhang

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.

Manindra Agrawal, Richard Beigel, Thomas Thierauf

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 >>>

Richard Beigel, Howard Straubing

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 >>>

Richard Beigel, William Gasarch, Efim Kinber

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 >>>

Richard Beigel

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.

Richard Beigel, David Eppstein

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 >>>