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, #Pcompleteness, Examples of counting problems, Permanent is #Pcomplete  Valiantâ€™s theorem, Quantifiers versus counting: ValiantVazirani 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, RazborovSmolensky 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. ImpagliazzoKabanets theorem. (4 lectures)
Learning Outcomes

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

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

Theory of Computation by Dexter C Kozen (ISBN13:9781846282973)

Computational Complexity: A modern approach by Sanjeev Arora and Boaz Barak (ISBN13:9780521424264)

Computational Complexity: A Conceptual Perspective by Oded Goldreich (ISBN13:9780521884730)

Theory of Computational Complexity by DingZu Du and KerI Ko. (ISBN13:9780471345060)

Introduction to Circuit Complexity: A Uniform Approach by Heribert Vollmer (ISBN13:9780324006384)

Boolean Function Complexity: Advances and Frontiers by Stasys Jukna (ISBN13:9783642245077)

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  3003 
Course Category  PME 
Proposing Faculty  Krishnamoorthy Dinesh 
Approved on  Senate 21 of IIT Palakkad 
Course prerequisites  Computational Complexity as a prerequisite 
Course status  New 