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?


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 :


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.