References on Circuit Lower Bounds

Question

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.)

Answer 1

What you want is a good reference to understand the exponential lower bounds for $AC^0$ circuits computing the PARITY function.

Now you haven't stated whether you actually want to understand the proof, or just understand things at a high level, the way a survey article would explain things.

A survey article I recently read and liked is "The complexity of finite functions" by Boppana and Sipser.

If you really want to sit down and understand the proof, then you can either read proofs based on the Switching lemma (which appear in the papers you cited - [FSS], [Y] and [H1]), or the Razborov-Smolensky proof.

For proofs using the Switching Lemma, Håstad's Ph.D. thesis is a good read, if a bit hard to follow if you're new to the area. A better exposition of the proof is in "Introduction to circuit complexity and a guide to Håstad's proof" by Allan Heydon. The only problem with it is that I can't find it online, and I have a hard copy. I really recommend it if you're new to circuit complexity.

For the Razborov-Smolensky approach, just google for it and you'll get a bunch of lecture notes. I understood the lower bound from these three lecture notes: Sanjeev Arora, Madhu Sudan and Kristoffer Arnsfelt Hansen.

Answer 2

If you find the exposition of the Switching Lemma in Hastad's thesis hard to follow, you can try Paul Beame's ``A Switching Lemma Primer'', which has a different version due to Razborov (which also explicitly uses decision trees, something that is crucial in some applications of the Switching Lemma)

Answer 3

This book is great for explaining lower bounds, if you have access to it.

Introduction to Circuit Complexity by Heribert Vollmer.

I just finished reading it, and although it says "introduction" is a very deep treatment on circuit complexity. It explains with details all (most popular) techniques for proving circuit lower bounds in chapter 3.

Answer 4

A more recent reference would be Boolean Function Complexity by Stasys Jukna. You just need to drop him an email or fill the form to get the pdf of the draft.

An older but still nice reference is the survey The Complexity of Finite Functions by Boppana and Sipser. This survey is very readable compared to other sources.

Another good reference is the book Boolean Functions and Computation Models by Clote and Kranakis.

Answer 5

I am no specialist, but there is probably interesting information in the blue book (http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/).

There is also a paper by Allender in 1997 : Circuit Complexity before the Dawn of the New Millennium

Answer 6

Emanuele Viola has published the book "On the Power of Small-Depth Computation" which includes many results on circuit lower bounds.

A preliminary version of the book can be found here.