Complexity Lower Bounds following Gowers' blog (Fall 2009)

Lecturer: Irit Dinur
Location: Ziskind 1
Time: Tuesdays 14:00 - 16:00


Syllabus: In the course we will follow posts of a blog of Tim Gowers in which he describes an attempt to prove complexity lower bounds, and in particular, P \neq NP. His posts take the form of a conversation that resembles the research process (generating ideas, ruling them out, and so on) as opposed to a finished result. There are 10 entries, topics include circuit lower bounds, complexity barriers, additive combinatorics, and random graphs. In the course of the semester we will learn about complexity lower bounds by following the blog posts, stopping to dive deeper into some of the technical material that they touch upon.

Requirements: Attendance, homework assignments, final project.

Exercises:

Problem Set #1: due December 15, 2009.