15
$\begingroup$

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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ Eventually, eventually :) $\endgroup$
    – Ryan Williams
    May 12, 2014 at 1:46
14
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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