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.

Past Offerings

Course Metadata

Item Details
Course Title Advanced Computational Complexity
Course Code CS6601
Course Credits 3-0-0-3
Course Category PME
Proposing Faculty Krishnamoorthy Dinesh
Approved on Senate 21 of IIT Palakkad
Course prerequisites Computational Complexity as a prerequisite
Course status New