This is a graduate course in computational complexity, including a mix of “classical” results, and a few very recent results from the last decade.
Complexity theory deals with the power of efficient computation. Here `efficiency’ could refer to any of the computational resources such as time, memory, communication, number of rounds of communication, and randomness.
While in the last century logicians and computer scientists developed a pretty good understanding of the power of finite time algorithms (where finite can be an algorithm that on on a 1000 bit input will take longer to run than the lifetime of the sun) our understanding of efficient algorithms is quite poor. Thus, complexity theory contains more questions, and relationships between questions, than actual answers. Nevertheless, we will learn about some fascinating insights, connections, and even few answers, that emerged from complexity theory research.
Complexity theory concerns itself with fundamental questions such as:
Apart from these general themes, this offering will have a special emphasis on concrete lower bounds for specific computational models. In particular, the course will explore at least a few of the following topics:
Meeting Time: Monday-Wednesday 10:30-12:00pm
Room: 380 SODA
Office Hours: Monday 1:30-2:30 at 623 SODA (or by appointment)
Piazza: piazza page
Resources: A major portion of the course will use chapters from
Grading: 50% Homeworks + 25% Final + 25% Class Participation
There will be a short homework consisting of 1-2 problems assigned every week. The homework is due on Thursday by 5pm.
Please email your solutions to firstname.lastname@example.org with Subj: “278 Homework #number” OR drop them in the mail box by the door at 623 Soda.
You are encouraged to discuss the problems and solve them in groups. However, the solutions are to be written up alone, listing all the collaborators.
There will be one take-home final at the end of the semester.
|Aug 24||Introduction,Turing Machines, Diagonalization||Sections 1.1, 1.2, 1.3, 1.4, 1.5.1 & 3.1|
|Aug 29||Nondeterminism, Cook's Theorem, NP-completeness, Definition of Polynomial Hierarchy||Chapter 2|
|Aug 31||PSPACE, PSPACE-completeness of TQBF, Definition of NL/coNL||Sections 4.1,4.2, Theorem 4.11|
|Sept 7||BPP||Section 7.1, 7.2, Lemma 7.9, Section 7.6|
|Sept 12||NL-completeness, Savitch's Theorem, NL=coNL,||Section 4.3.1, 4.4|
|Sept 14||Interactive Proofs||Section 8.1,8.2,8.3,8.4.1|
|Sept 19||coNP in IP||Section 8.5.1,8.5.2|
|Sept 21||PSPACE in IP||Section 8.5.3|
|Sept 26||Cryptography||Section 10.1, 10.2|
|Sept 28||Goldreich-Levin algorithm for learning linear functions||section 10.3|
|Oct 3||PRG from one-way permutation, commitments, zero-knowledge proofs|
|Oct 5||PCP Theorem and hardness of approximation||Section 18.1,18.2|
|Oct 10||Exponential sized PCP||Section 18.4.1,18.4.2|
|Oct 12||Non-uniform Models of Computation - Circuits,Branching Programs, Formulas||Lecture notes by Madhu Sudan|
|Oct 17||Razborov-Smolensky's ACC lower bound||Lecture notes by Madhu Sudan|
|Oct 19||Formulas size lower bound for Element Distinctness||Lecture notes by Madhu Sudan|
|Oct 24||Communication Complexity -- Karchmer-Wigderson Games, Protocols and Rectangles, Fooling Set||Lecture Notes by Mark Braverman Sec 2.2 in Lecture Notes by Prahladh Harsha|
|Oct 26||Randomized Communication Complexity, Min-Max, Discrepancy, Inner product function||Lecture Notes by Prahlad Harsha|
|Oct 31||Applications of Communication Complexity: Streaming lower bounds, Monotone Depth||Section 2.2.1 in lecture notes by Prahlad Harsha Section 5.1 in lecture notes by Prahlad Harsha|
|Nov 2||Basics of Information Theory||lecture1 lecture 2 by Mark Braverman|
|Nov 7||Communication Lower Bound for Disjointness||Lecture Notes by Prahladh Harsha (Sec 11.2)|
|Nov 9||Proof Complexity||Lecture Notes by Paul Beame and Ashish Sabharwal (Sec 1.1, 1.2, 2.1) Introduction to sum-of-squares proof system in paper by O'Donnell and Zhou|
|Nov 14||Time-Bounded Derandomization||Lecture notes by Dieter Van Melkebeek|
|Nov 16||Expanders||Chapter 4 in Salil Vadhan's monograph|
|Nov 21||Space-Bounded Derandomization||Lecture notes by Dieter Van Melkebeek|
|Nov 28||Relativization and Natural Proofs||Chapter 22|
|Nov 30||Fine-Grained Complexity within P||Survey by Virginia V. Williams|