All reports by Author Amihood Amir:

__
TR00-024
| 16th May 2000
__

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

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