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 :
