**Lectures**Hill 120, Tuesdays and Thursdays 3.20-4.40**Instructor**Andrej Bogdanov, adib(a)dimacs.rutgers.edu, CoRE 413. Office hours Thu 1-2 or by appointment.**Teaching Assistant**Nikolaos Leonardos, nileonar(a)cs.rutgers.edu. Office hours Mon 4-6.

**Apr 24**See the project presentation schedule for Thu Apr 26.**Apr 21**The project reports are due by Mon Apr 30 (preferably by e-mail, but if you want to turn in a hard copy slide it under my door).**Apr 19**Please email me the title of your project presentation.**Apr 19**Project presentations will be in class on Thu Apr 26. Each presentation should take about 20 minutes. We will probably run a bit overtime so please let me know if you need to leave early.

Computational complexity studies the inherent power and limitations of various computational processes, be they natural, engineered, or imaginary. Here are some examples:

- Is every problem whose solutions are easy to verify also easy to solve?
- If not, can we still solve the problem on most instances, or solve it approximately?
- If yes, is it also easy to count how many solutions there are?
- What things can you be convinced of in a short conversation?
- Can random coins be used to speed up computations, or the checking of proofs?

Complexity theory does not yet know the answers to these questions, but it shows that they (and many others) are deeply interconnected. In this course we will study the methodology and some of the tools that are used to establish these connections.

The course will cover ''classical'' topics in complexity theory as well as some recent developments.

date | topic | |
---|---|---|

1 | Jan 16 | Introduction, P and NP
Notes: Arora-Barak Chapters 1 and 2, Trevisan Lecture 1 |

2 | Jan 18 | NP completeness, hierarchy theorems
Notes: Arora-Barak Chapter 3, Trevisan Lecture 1 |

3 | Jan 23 | The polynomial hierarchy, oracles
Notes: Arora-Barak Chapter 5, Trevisan Lecture 3 |

4 | Jan 25 | Circuits, Karp-Lipton-Sipser theorem
Notes: Trevisan Lecture 4 |

5 | Jan 30 | Randomized algorithms, polynomial identity testing
Notes: Trevisan Lectures 5, 6 |

6 | Feb 1 | More on BPP, unique solutions
Notes: Trevisan Lectures 5, 7 |

7 | Feb 6 | Counting problems, approximate counting
Notes: Trevisan Lecture 8 |

8 | Feb 8 | Toda's theorem
Notes: Proof of Toda's theorem |

9 | Feb 13 | Worst-case and average-case equivalence for #P
Notes: Trevisan Lecture 9 |

10 | Feb 15 | Average-case complexity for NP
Notes: Average-case complexity |

11 | Feb 20 | Average-case completeness
Notes: From last lecture |

12 | Feb 22 | One-way functions and pseudorandom generators
Notes: One-way functions and pseudorandom generators |

13 | Feb 27 | The Goldreich-Levin theorem
Notes: Arora-Barak Chapter 10, Section 3 |

14 | Mar 1 | Space complexity
Notes: Trevisan Lecture 2 |

15 | Mar 6 | Interactive proofs
Notes: Arora-Barak Chapter 8, Trevisan Lecture 13 |

16 | Mar 8 | Interactive proofs for PSPACE
Notes: IP = PSPACE |

17 | Mar 20 | PCPs and constraint satisfaction problems
Notes: Arora-Barak §18.1, §18.2 |

18 | Mar 22 | Local testing and local decoding
Notes: Arora-Barak §18.4 |

19 | Mar 27 | Expanders and eigenvalues
Notes: Random walks and expanders |

20 | Mar 29 | More on expanders; the PCP theorem
Notes: From last lecture; Arora-Barak §18.5 |

21 | Apr 3 | Arity reduction, regularizing, expanderizing
Notes: Arora-Barak §18.5, omitted proofs |

22 | Apr 5 | Alphabet reduction, gap amplification
Notes: Arora-Barak §18.5 |

23 | Apr 10 | Finish gap amplification; Circuit lower bounds
Notes: Trevisan lecture 19 |

24 | Apr 12 | Lower bounds for constant depth circuits via polynomials
Notes: Trevisan lecture 19 |

Apr 17 | Classes cancelled campuswide | |

25 | Apr 19 | Circuit lower bounds via the switching lemma
Notes: Trevisan lecture 20 |

26 | Apr 24 | Relativizing proofs and natural proofs
Notes: Arora-Barak §3.5, Chapter 22 |

27 | Apr 26 | Project presentations |

- Homework 4 due Tue Apr 10 and solutions
- Homework 3 due Tue Mar 20 and solutions
- Homework 2 due Tue Feb 20 and solutions
- Homework 1 due Tue Feb 6 and solutions

In the first part of the course we will focus on the following topics.

**Basic complexity classes**P and NP, decision versus search, diagonalization and its limitations, the polynomial-time hierarchy, non-uniform models.**Randomness and counting**Randomized complexity classes, counting solutions, Valiant-Vazirani, approximate counting, Toda's theorem.**Small space computations**L and NL, Savitch theorem, NL = coNL, graph connectivity and randomized logspace.**Interactive proofs**AM and IP, round reduction, AM versus NP, IP versus PSPACE.

Here are some topics that we may talk about in the second part. This list should provide a representative sample though I do not expect we will have enough time to touch upon all of them.

**Average-case complexity**Distributional problems, heuristic algorithms, average-case completeness, one-way functions, random self-reductions, hardness amplification.**Pseudorandomness**The Nisan-Wigderson generator, expanders and Reingold's theorem, Goldreich-Levin theorem and cryptographic generators.**Circuit lower bounds**Bounds for small depth circuits, connection to pseudorandomness, natural proof limitations.**Inapproximability**The PCP theorem, combinatorial view of proof systems, gap amplification, parallel repetition, Håstad's verifier for 3SAT.

**Prerequisites**198:509 (Foundations of computer science) and 198:513 (Data structures and algorithms), or familiarity with discrete mathematics, algorithms, and proofs.**Sources**Our main sources for the course are Luca Trevisan's lecture notes on complexity and the draft of the book Complexity theory: A modern approach by Sanjeev Arora and Boaz Barak. A good reference for some of the material is the draft of another new book by Oded Goldreich.**Grading and homeworks**Your grade will be determined from class attendance, homeworks, and possibly a final project (if class size allows it). Homeworks will be issued periodically, and you are encouraged to collaborate on them as long as you write up your own solutions.**Final project**For your final project you will be expected to do a bit of independent reading, a short presentation in class, and a short report.