<p>Yes, yes, and yes. </p>

<p>The basic idea is to consider the characteristic function of a language $L$ 
(the oracle you're constructing) at length $n$ as a string of length $2^n$ 
that will be an input to a ("big") circuit. 
An OR gate in that circuit will correspond to 
a polynomially-bounded existential quantifier, and 
an AND gate to a polynomially-bounded universal quantifier. </p>

<p>Consider Furst-Saxe-Sipser as an example of 
how this can be used to build oracles:<br>
If the language $L$ is constructed so that 
the characteristic function of $L \cap \Sigma^n$ is an input 
whose parity differs from an $\mathsf{AC}^0$ function 
(which exists, by Furst-Saxe-Sipser), 
then you've just successfully diagonalized against 
the language in $\mathsf{PH}$ corresponding to that $\mathsf{AC}^0$ function.
Doing this over all $\mathsf{AC}^0$ diagonalizes against all of $\mathsf{PH}$, and thus builds an oracle $L$ such that $\mathsf{PH}^L \neq \mathsf{PSPACE}^L$
(since the latter includes the language corresponding to 
the "big" parity circuit).</p>

<p>For more discussion and examples of this general theme see the following survey :</p>

<ul>
<li>Ker-I Ko, "<a href="http://www3.cs.stonybrook.edu/~keriko/survey2.pdf" rel="noreferrer">Constructing Oracles by Lower Bound Techniques for Circuits</a>", 1989.</li>
</ul>

CC BY-SA 3.0
2015-11-03T05:12:36.260Z
2015-11-03T08:43:58.067Z
2015-11-03T08:43:58.067Z
Joshua Grochow
<p>I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation. </p>

<p>Can someone explain how proving lower bounds for circuits and constructing oracles separating complexity classes are related?<br>
Are there other circuit lower bounds related to separating oracles?<br>
Is there a general theme connecting nonuniform lower bounds for circuits and  separating oracles?</p>

<cc.complexity-theory><circuit-complexity><lower-bounds><big-picture><oracles>
Lower bounds for nonuniform circuits and oracles separating complexity classes
Anonymous
# Lower bounds for nonuniform circuits and oracles separating complexity classes

(Asked by: username_0 on 2015-10-15)

I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation.

Can someone explain how proving lower bounds for circuits and constructing oracles separating complexity classes are related?  
Are there other circuit lower bounds related to separating oracles?  
Is there a general theme connecting nonuniform lower bounds for circuits and separating oracles?

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, big-picture, oracles

---

## 1 answers

### Answer by username_1 on 2015-11-03. Score: 7 | Accepted answer

Yes, yes, and yes.

The basic idea is to consider the characteristic function of a language $L$
(the oracle you're constructing) at length $n$ as a string of length $2^n$
that will be an input to a ("big") circuit.
An OR gate in that circuit will correspond to
a polynomially-bounded existential quantifier, and
an AND gate to a polynomially-bounded universal quantifier.

Consider Furst-Saxe-Sipser as an example of
how this can be used to build oracles:  
If the language $L$ is constructed so that
the characteristic function of $L \cap \Sigma^n$ is an input
whose parity differs from an $\mathsf{AC}^0$ function
(which exists, by Furst-Saxe-Sipser),
then you've just successfully diagonalized against
the language in $\mathsf{PH}$ corresponding to that $\mathsf{AC}^0$ function.
Doing this over all $\mathsf{AC}^0$ diagonalizes against all of $\mathsf{PH}$, and thus builds an oracle $L$ such that $\mathsf{PH}^L \neq \mathsf{PSPACE}^L$
(since the latter includes the language corresponding to
the "big" parity circuit).

For more discussion and examples of this general theme see the following survey :

* Ker-I Ko, "[Constructing Oracles by Lower Bound Techniques for Circuits](http://www3.cs.stonybrook.edu/~keriko/survey2.pdf)", 1989.


---

