Good text on introduction to circuit complexity

Question

I would like to ask suggestions for good texts which introduce circuit complexity. Any pointers to recent advances and open problems in this field would also be helpful.

score 14 · Accepted Answer · answered May 11 '14 at 06:38

14

To start off, there is of course Arora and Barak's book Computational Complexity: A Modern Approach. From there, parts 3 and 4 of Jukna's book Boolean Function Complexity: Advances and Frontiers make excellent reading material. Also, Ryan Williams teaches a nice course on circuit complexity whose course notes might hopefully be put up online :)

answered May 11 '14 at 06:38

arnab

7,000
1
38
55

6

Eventually, eventually :) – Ryan Williams May 12 '14 at 01:46

score 14 · Answer 2 · answered May 11 '14 at 15:08

14

In addition to the ones suggested by Arnab, I would also recommend the following book:

Introduction to Circuit Complexity: A Uniform Approach by Heribert Vollmer

answered May 11 '14 at 15:08

Robin Kothari

13,617
2
60
116

score 1 · Answer 3 · answered May 12 '14 at 21:09

Models of Computation by John E Savage (more info/detail/reviews on amazon). its largely more of an undergraduate textbook but is notable for its circuit-centric point of view. includes many advanced topics/proofs, and its free online, and is very well hyperlinked (TOC, refs, index, etc).

Good text on introduction to circuit complexity

3 Answers3