Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

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


previous PreviousNext next


ISSN 1433-8092 | Imprint