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.