Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 13 down vote accepted

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

share|cite|improve this answer
Eventually, eventually :) – Ryan Williams May 12 '14 at 1:46

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.