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.