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

<p><a href="http://rads.stackoverflow.com/amzn/click/3540643109">Introduction to Circuit Complexity</a> by Heribert Vollmer.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-28T22:52:33.607Z
2010-09-28T22:52:33.607Z
Marcos Villagra
<p>If you find the exposition of the Switching Lemma in Hastad's thesis hard to follow, you can try Paul Beame's <a href="http://www.cs.washington.edu/homes/beame/papers/primer.ps">``A Switching Lemma Primer''</a>, 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) </p>

CC BY-SA 2.5
2010-09-28T22:34:34.103Z
2010-09-28T22:48:36.263Z
2010-09-28T22:48:36.263Z
Srikanth
<p>A more recent reference would be <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC.html">Boolean Function Complexity</a> by Stasys Jukna. You just need to drop him an email or fill the form to get the pdf of the draft.</p>

<p>An older but still nice reference is the survey <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/boppana_sipser.ps">The Complexity of Finite Functions</a> by Boppana and Sipser. This survey is very readable compared to other sources.</p>

<p>Another good reference is the book <a href="http://rads.stackoverflow.com/amzn/click/3540594361">Boolean Functions and Computation Models</a> by Clote and Kranakis.</p>

CC BY-SA 2.5
2010-09-28T21:33:18.587Z
2010-12-07T02:03:28.820Z
2010-12-07T02:03:28.820Z
Dai Le
<p>I am no specialist, but there is probably interesting information in the blue book (<a href="http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/" rel="nofollow">http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/</a>).</p>

<p>There is also a paper by Allender in 1997 : <a href="http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf" rel="nofollow">Circuit Complexity before the Dawn of the New Millennium</a></p>

CC BY-SA 2.5
2010-09-28T20:50:57.203Z
2010-09-28T20:50:57.203Z
Sylvain Peyronnet
<p>Emanuele Viola has published the book "<a href="http://www.nowpublishers.com/product.aspx?product=TCS&amp;doi=0400000033" rel="nofollow">On the Power of Small-Depth Computation</a>" which includes many results on circuit lower bounds.</p>

<p>A preliminary version of the book can be found <a href="http://www.ccs.neu.edu/home/viola/papers/shallow.pdf" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2011-04-15T13:18:45.533Z
2011-04-15T13:18:45.533Z
Sadeq Dousti
<p>What you want is a good reference to understand the exponential lower bounds for $AC^0$ circuits computing the PARITY function.</p>

<p>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. </p>

<p>A survey article I recently read and liked is "<a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/boppana_sipser.ps">The complexity of finite functions</a>" by Boppana and Sipser.</p>

<p>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.</p>

<p>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 Hå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.</p>

<p>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: <a href="http://www.cs.princeton.edu/courses/archive/fall02/cs597D/lec5.ps">Sanjeev Arora</a>, <a href="http://people.csail.mit.edu/madhu/ST05/scribe/lect06.pdf">Madhu Sudan</a> and <a href="http://www.cs.au.dk/~arnsfelt/CT08/scribenotes/lecture10.pdf">Kristoﬀer Arnsfelt Hansen</a>.</p>

CC BY-SA 3.0
2015-02-01T17:02:06.427Z
I finally got a link to Allan Heydon's technical report on [CMU repository](http://repository.cmu.edu/cgi/viewcontent.cgi?article=3006&context=compsci&sei-redir=1).
Sadeq Dousti
CC BY-SA 2.5
2010-09-29T02:39:59.267Z
Do you suggest any way to obtain a copy of of Allan Heydon's exposition of the proof?
Sadeq Dousti
CC BY-SA 2.5
2010-09-29T11:23:36.987Z
@Sadeq: No idea. I got it from my library. It's listed on CMU's tech reports page (http://www.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.
Robin Kothari
CC BY-SA 2.5
2010-09-28T22:13:18.190Z
2010-09-28T22:13:18.190Z
Robin Kothari
<h3>Preamble</h3>

<p>Interactive proof systems and Arthur-Merlin protocols were introduced by <a href="http://portal.acm.org/citation.cfm?id=22145.22178">Goldwasser, Micali and Rackoff</a> and <a href="http://portal.acm.org/citation.cfm?id=22145.22192">Babai</a> back in 1985. At first, it was thought that the former is more powerful than the latter, but <a href="http://portal.acm.org/citation.cfm?id=12130.12137">Goldwasser and Sipser</a> showed that they have the same power (with respect to language recognition). Hence, in this post, I'll used the two concepts interchangeably.</p>

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

<p>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: <a href="http://dx.doi.org/10.1016/0020-0190(88)90199-8">Fortnow and Sipser</a> 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$.)</p>

<p>On the other hand, the following paper:</p>

<p><code>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= <a href="http://dx.doi.org/10.1109/SFCS.1986.36">http://dx.doi.org/10.1109/SFCS.1986.36</a></code></p>

<p>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}$.)</p>

<hr>

<h3>The Question</h3>

<p>The paper by Aiello, Goldwaseer, and Hastad (cited above) states:</p>

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

<p>where [FSS], [Y] and [H1] are:</p>

<p><code>[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.</code></p>

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

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

<p>I found the papers very old and extremely hard to follow. I read Chapter 14 of <a href="http://rads.stackoverflow.com/amzn/click/0521424267">Arora &amp; Barak's book</a>, yet apparently it does not cover everything I need.</p>

<blockquote>
  <p>What references on "Circuit Lower Bounds" do you suggest?</p>
</blockquote>

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

CC BY-SA 2.5
2010-11-30T22:35:11.013Z
yet another reference: [lecture notes of Avi Wigderson](http://intractability.princeton.edu/wp-content/uploads/2009/05/avicircuits.pdf) on lower bounds for constant depth and monotone circuits (this link is from the Arora-Barak draft website).
Alessandro Cosentino
<cc.complexity-theory><lower-bounds><circuit-complexity>
References on Circuit Lower Bounds
Sadeq Dousti
# References on Circuit Lower Bounds

(Asked by: username_0 on 2010-09-28)

### Preamble

Interactive proof systems and Arthur-Merlin protocols were introduced by [Goldwasser, Micali and Rackoff](http://portal.acm.org/citation.cfm?id=22145.22178) and [Babai](http://portal.acm.org/citation.cfm?id=22145.22192) back in 1985. At first, it was thought that the former is more powerful than the latter, but [Goldwasser and Sipser](http://portal.acm.org/citation.cfm?id=12130.12137) 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](http://dx.doi.org/10.1016/0020-0190(88)90199-8) 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](http://rads.stackoverflow.com/amzn/click/0521424267), 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.)

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity
> **Comments:**
> **username_1**: yet another reference: [lecture notes of Avi Wigderson](http://intractability.princeton.edu/wp-content/uploads/2009/05/avicircuits.pdf) on lower bounds for constant depth and monotone circuits (this link is from the Arora-Barak draft website).  

---

## 6 answers

### Answer by username_6 on 2010-09-28. Score: 15 | Accepted answer

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](http://www.cs.umd.edu/~gasarch/BLOGPAPERS/boppana_sipser.ps)" 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 Hå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](http://www.cs.princeton.edu/courses/archive/fall02/cs597D/lec5.ps), [Madhu Sudan](http://people.csail.mit.edu/madhu/ST05/scribe/lect06.pdf) and [Kristoﬀer Arnsfelt Hansen](http://www.cs.au.dk/~arnsfelt/CT08/scribenotes/lecture10.pdf).

> **Comments:**
> **username_0**: Do you suggest any way to obtain a copy of of Allan Heydon's exposition of the proof?  
> **username_6**: @Sadeq: No idea. I got it from my library. It's listed on CMU's tech reports page (http://www.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.  
> **username_0**: I finally got a link to Allan Heydon's technical report on [CMU repository](http://repository.cmu.edu/cgi/viewcontent.cgi?article=3006&context=compsci&sei-redir=1).  

---

### Answer by username_2 on 2010-09-28. Score: 14

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

[Introduction to Circuit Complexity](http://rads.stackoverflow.com/amzn/click/3540643109) 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 by username_3 on 2010-09-28. Score: 14

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''](http://www.cs.washington.edu/homes/beame/papers/primer.ps), 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 by username_4 on 2010-09-28. Score: 12

A more recent reference would be [Boolean Function Complexity](http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC.html) 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](http://www.cs.umd.edu/~gasarch/BLOGPAPERS/boppana_sipser.ps) by Boppana and Sipser. This survey is very readable compared to other sources.

Another good reference is the book [Boolean Functions and Computation Models](http://rads.stackoverflow.com/amzn/click/3540594361) by Clote and Kranakis.


---

### Answer by username_5 on 2010-09-28. Score: 10

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](http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf)


---

### Answer by username_0 on 2011-04-15. Score: 4

Emanuele Viola has published the book "[On the Power of Small-Depth Computation](http://www.nowpublishers.com/product.aspx?product=TCS&doi=0400000033)" which includes many results on circuit lower bounds.

A preliminary version of the book can be found [here](http://www.ccs.neu.edu/home/viola/papers/shallow.pdf).


---

