Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

ISSN 1433-8092 | Imprint