# Computational complexity

## General information

• Lectures
• Omar Fawzi
• Wednesdays 10:15 to 12:15
• Tutorials
• Eugenia Oschurku
• Thursdays 13:30 to 15:30
This course will cover the basics of computational complexity theory. We will try to cover the following topics.
• Models of computation. Time and space classes.
• Randomized complexity classes
• Boolean circuits
• Interactive proofs
• One of the following topics: communication complexity, quantum complexity theory, Hardness of approximation and PCPs

## Grading

The grading scheme will take into account
• A final exam
• Several homeworks
• One midterm exam
The general policy is that 1/2 of the grade is determined by the final exam.

## Schedule

 Date Topic References Jan 30th The class P and the class NP. Nondeterministic Turing machines, equivalent definition of NP. NP-hardness. Example NP-complete problem. Statement of NP-completeness of SAT Lecture notes (from 2014 offering) Chap 1 of [AB], Sec 2.1, 2.2 and beginning of 2.3 of [AB] Feb 6th Proof that SAT is NP-hard. (Check these notes for a proof of NP-completeness of SAT for a RAM model.) Class coNP. NP and coNP are in EXP. Deterministic time hierarchy theorem. Chap 2 et 3.1 of [AB] Feb 13th Space complexity. L, NL, PSPACE. Relation to time classes. TQBF is PSPACE complete. Chap 4.1 and 4.2 of [AB] Feb 27th Space hierarchy theorem. Composition theorem for space. NSPACE(S) in SPACE(S^2) (Savitch theorem). Class NL, NL-hardness PATH is NL-complete. State NL = coNL. Sec 4.2 and 4.3 (space complexity) of [AB] Mar 6th Oracle Turing machines. Existence of oracles A,B with P^A=NP^A and P^B \neq NP^B. Polynomial hierarchy. If \Sigma_i = \Pi_i then the hierarchy collapses. Chap 3 and 5 in [AB] Mar 13th Midterm exam. Definition of polynomial hierarchy with oracles. Start boolean circuits. Chap 5 of [AB] Mar 20th Boolean circuits, P included in P/poly, uniformity condition for circuit family TMs with advice, Karp-Lipton theorem: If NP included in P/poly, then the polynomial hierarchy collapses. Chap 6 of [AB] Mar 27th Randomized computation: BPP, relation to P/poly and polynomial hierarchy. Chap 7 of [AB] Apr 3rd Communication complexity. Lower bound using fooling set bound, equality and disjointness. Chap 13 of [AB] Apr 10rd Communication complexity. Application to streaming lower bounds. Randomized communication complexity. Discrepency method and application to the inner product function. Chap 13 of [AB]