Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with bounded queries:
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 >>>

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

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

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

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

ISSN 1433-8092 | Imprint