References on Circuit Lower Bounds

Preamble

Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than the latter, but Goldwasser and Sipser showed that they have the same power (with respect to language recognition). Hence, in this post, I'll used the two concepts interchangeably.

Let $IP[k]$ be the class of languages admitting an interactive proof system with $k$ rounds. Babai proved that $IP[O(1)] \subseteq \Pi_2^P$. (A relativizable result.)

At first, it was not know whether unbounded number of rounds can increase the power of IP. In particular, it was shown to have contradictory relativizations: Fortnow and Sipser showed that for some oracle $A$, it holds that $coNP^A \not\subset IP[poly]^A$. (Therefore, relative to $A$, $IP[poly]$ is not a superclass of $PH$.)

On the other hand, the following paper:

Aiello, W., Goldwasser, S., and Hastad, J. 1986. On the power of interaction. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (October 27 - 29, 1986). SFCS. IEEE Computer Society, Washington, DC, 368-379. DOI= http://dx.doi.org/10.1109/SFCS.1986.36

shows that, for some oracle $B$, we have $IP[poly]^B \not\subset PH^B$. (Therefore, $IP[poly]^B \neq IP[O(1)]^B$ since as stated above, the latter is a subclass of $\Pi_2^{P,B}$.)

The Question

The paper by Aiello, Goldwaseer, and Hastad (cited above) states:

The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in [FSS], [Y] and [H1].

where [FSS], [Y] and [H1] are:

[FSS] Furst M., Saxe J. and Sipser M., "Parity, Circuits, and the Polynomial Time Hierarchy," Proceedings 22nd Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.

[Y] Yao A. "Separating the Polynomial-Time Hierarchy by Oracles," Proceedings of 6th Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10.

[H1] Hastad J. "Almost optimal lower bounds for small depth circuits," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 6-20.

I found the papers very old and extremely hard to follow. I read Chapter 14 of Arora & Barak's book, yet apparently it does not cover everything I need.

What references on "Circuit Lower Bounds" do you suggest?

(I specially need survey-like references; those which are newer and do not need a lot of expertise are more preferable.)

Asked by user873 (16,339 )
Sep 28, 2010 at 20:11