Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers 3

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|improve this answer
5  
Eventually, eventually :) –  Ryan Williams May 12 at 1:46
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.