- cc.complexity-theory lower-bounds circuit-complexity
- Updated Mon, 20 Jun 2022 10:47:37 GMT

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

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, Hstad'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 Hastad'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 Kristoer Arnsfelt Hansen.

- +0 – Do you suggest any way to obtain a copy of of Allan Heydon's exposition of the proof? — Sep 29, 2010 at 02:39
- +0 – @Sadeq: No idea. I got it from my library. It's listed on CMU's tech reports page (cs.cmu.edu/~clamen/reports/1990.html) as a tech report as CMU-CS-90-141, but there's no link to download or find it anywhere online. You could try emailing the author. — Sep 29, 2010 at 11:23
- +1 – I finally got a link to Allan Heydon's technical report on CMU repository. — Feb 01, 2015 at 17:02

External links referenced by this document:

- http://dx.doi.org/10.1016/0020-0190(88)90199-8
- http://dx.doi.org/10.1109/SFCS.1986.36
- http://people.csail.mit.edu/madhu/ST05/scribe/lect06.pdf
- http://portal.acm.org/citation.cfm?id=12130.12137
- http://rads.stackoverflow.com/amzn/click/0521424267
- http://www.cs.au.dk/~arnsfelt/CT08/scribenotes/lecture10.pdf
- http://www.cs.princeton.edu/courses/archive/fall02/cs597D/lec5.ps
- http://www.cs.umd.edu/~gasarch/BLOGPAPERS/boppana_sipser.ps