Requires CS5616 Computational Complexity as a prerequisite

# Course Objective

This is a topics/advanced course in computational complexity theory to serve as a follow up on the first course CS5616 Computational Complexity. The objective is to expose the student to a set of seemingly unrelated topics from circuit complexity, randomness and computing, lower bounds and derandomization and bring out how they are related.

# Course Content

Brief review of basic complexity classes and definitions. (1 lecture)

Counting complexity – Counting classes: #P, FP, GapP, Parsimonious reductions, #P-completeness, Examples of counting problems, Permanent is #P-complete - Valiant’s theorem, Quantifiers versus counting: Valiant-Vazirani Lemma, Unique SAT, randomized reductions, Toda’s theorem (8 lectures)

Circuit Complexity – Sequential versus parallel computation. Boolean circuits, basis and complete basis. Shannon’s lower bound, Lupanov’s upper bound, Circuit complexity classes – NC, SAC, AC and their relation to other complexity classes. Constant depth reductions. (6 lectures)

Space bounded computation – Branching programs, Bounded width branching programs and Barrington’s theorem. (4 lectures)

Circuit lower bounds – Gate elimination technique, Formula lower bounds - Subbotovskaya and Neciporuk’s lower bound, Random restrictions, Parity cannot be computed by AC0 circuits, Razborov-Smolensky polynomial approximation method and ACC lower bounds. Razborov’s proof of clique lower bounds for monotone circuits. (12 lectures)

Interactive Proofs – Motivation and definition, AM, MA proof systems. Sum check protocol. Random self reducibility and interactive proof for Permanent (7 lectures)

Hardness versus Randomness - Pseudorandom generators, Nisan Wigderson generator, Derandomizing BPP under worst case assumption. Impagliazzo-Kabanets theorem. (4 lectures)

# Learning Outcomes

1. Being able to understand and appreciate the fundamental notions of reductions, ideas of hardness, completeness, randomness and proofs.

2. Get a deeper understanding of the power and limitations of related computational models like branching programs and Boolean circuits and their relation to Turing machines.

# Text/Reference Books

1. Theory of Computation by Dexter C Kozen (ISBN-13:978-1846282973)

2. Computational Complexity: A modern approach by Sanjeev Arora and Boaz Barak (ISBN-13:978-0521424264)

3. Computational Complexity: A Conceptual Perspective by Oded Goldreich (ISBN-13:978-0521884730)

4. Theory of Computational Complexity by Ding-Zu Du and Ker-I Ko. (ISBN-13:978-0471345060)

5. Introduction to Circuit Complexity: A Uniform Approach by Heribert Vollmer (ISBN-13:978-0324006384)

6. Boolean Function Complexity: Advances and Frontiers by Stasys Jukna (ISBN-13:978-3642245077)

7. A selected subset of latest research papers and surveys.