Skip to content


October 31, 2012

Welcome to Topics in Circuit Lower Bounds, Weizmann 2012/3.

Syllabus: we start the course by understanding what circuits are and why circuit lower bounds are interesting. Specifically, we will understand their role in separating P from NP. During this part we will encounter important complexity classes such as the polynomial hierarchy as well as the notions of oracles and relativizing results. We then turn to discuss restricted circuit families such as AC0 and show a classical result by Razborov-Smolensky – a result that motivated Williams’ result.

Proving Williams’ result will require more background in computational complexity. Thus, we introduce the notions of randomization in computation, derandomization, interactive proofs, and the complexity of counting, in depth. For example, we will prove (either in class or in your talks, at the end of the semester) classical results such as IP=PSPACE, Toda’s theorem, the completeness of the permanent, derandomization using Nisan-Wigderson pseudorandom generator, and more.

At this point we will be ready to prove a beautiful result by Impagliazzo-Kabanets – derandomization implies circuit lower bounds. Equipped with all these results and ideas we can finally prove Williams’ theorem.

In the last part of the course we will discuss the classical problem of explicitly constructing rigid matrices, and its relation to circuit lower bounds, due to Valiant.

The grade for the course will be determined by two factors. 1) lecture notes that each student will be asked to write, which counts for half of the grade; and 2) towards the end of the semester, a list of papers related to the course will be published. Each student will be asked to select a paper out of the list, and give a clear and detailed 50-90 minute, white-board talk, presenting the paper of choice. The participation of students in fellow student talks is recommended but not obligated.



From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: