__
TR05-040 | 13th April 2005 00:00
__

#### Oracles Are Subtle But Not Malicious

**Abstract:**
Theoretical computer scientists have been debating the role of

oracles since the 1970's. This paper illustrates both that oracles

can give us nontrivial insights about the barrier problems in

circuit complexity, and that they need not prevent us from trying to

solve those problems.

First, we give an oracle relative to which PP has linear-sized

circuits, by proving a new lower bound for perceptrons and low-

degree threshold polynomials. This oracle settles a longstanding

open question, and generalizes earlier results due to Beigel and to

Buhrman, Fortnow, and Thierauf. More importantly, it implies the

first nonrelativizing separation of "traditional" complexity classes,

as opposed to interactive proof classes such as MIP and MA-EXP. For

Vinodchandran showed, by a nonrelativizing argument,

that PP does not have circuits of size n^k for any fixed k. We

present an alternative proof of this fact, which shows that PP does

not even have quantum circuits of size n^k with quantum advice. To

our knowledge, this is the first nontrivial lower bound on quantum

circuit size.

Second, we study a beautiful algorithm of Bshouty et al. for learning

Boolean circuits in ZPP^NP. We show that the NP queries in

this algorithm cannot be parallelized by any relativizing technique,

by giving an oracle relative to which ZPP^||NP and even BPP^||NP

have linear-size circuits. On the other hand, we also show that the

NP queries could be parallelized if P=NP. Thus, classes such as

ZPP^||NP inhabit a "twilight zone," where we need to distinguish

between relativizing and black-box techniques. Our results on this

subject have implications for computational learning theory as well

as for the circuit minimization problem.