June, 2017

Complexity theory studies what problems can and cannot be solved by computers given limited running time and memory resources.

Students are expected to read the corresponding chapter from the textbook (mentioned under readings), before attending the lecture. The lecture is mainly for clearing doubts and covering the most confusing parts.

The is a short course with 13 lectures for students who might not have taken a Theory of Computation course. However sufficient knowledge of discrete maths and algorithms is assumed. It is not supposed to be a rigorous one, for research student, but rather an introduction to field of complexity theory.

- Wednesday (10:00 a.m.-11:25 a.m., Venue: 205)
- Saturday (10:00 a.m.-11:25 a.m., Venue: 205)
- Tutorial : Saturday (3:30 p.m.-4:30 p.m., Venue: 204)

Short notes are available with additional references : Consolidated Notes HTML.

**Introduction**

Decision Problems | Turing Machines | Efficient Algorithms**Paradox’s, Diagonalization, Undecidablility**

Russell’s Paradox and Diagonalization | Universal Turing Machines | Halting Problem**Nondeterminism, NP and Search Problems**

Non Deterministic Turing Machines | Nondeterministic Polynomial Time : NP | NP : Verifier Definition | Descision vs Search Problems**Reductions, NP-Completenesss & Cooks Theorem**

Polynomial Time Reductions | Cook-Levin Theorem | NP Compeleness / Hardness**More Time Complexity**

NP-completeness of Vertex Cover and Subset Sum | EXP and Time Heirachy Theorem | coNP and Map of Complexity classes**Space Compleixty**

Space Complexity classes and some Relationships | Non Determinism and Space : NL-complete, Savith’s Theorem | Overview of next part of course**NL = coNL, Randomization**

Recapping Nondeterminism | Immerman-Szelepcsenyi Theorem : NL = coNL | Randomized TMs and Complexity Classes**Randomized Algorithms**

BPP and Amplification | Approx MAX-CUT | Undirected REACHABILITY in RL**Random Walks, Derandomization and Polynomial Identity Testing**

Analysis of Random Walks | Derandomizing MaxCUT | Randomization: PIT and Schwartz-Zippel Lemma**Streaming Algorithms and Lowerbounds**

Schwartz Zippel Lemma Proof | Lowerbound for Bracket Matching | Randomized Streaming Algorithm for Bracket Matching**Property Testing**

Property Testing Model | Linearity Test by Blum, Luby and Rubinfield**PAC Learning**

hugo

This part of the course will have a total of 50 marks + 5 bonus marks.

- 25 marks for the end sem.
- 15 marks for the mid sem.
- 10 marks for assignments.
- 5 marks for quiz.

2-3 question will be given out at the end of every lecture. There will be one tutorial session per week (to be scheduled), where the assignments for the previous week will be collected, and solutions will be discussed.

**Textbook : Computational Complexity by Christos Papadimitriou**

Some courses offered elsewhere:

- [Sud] A course on complexity theory (offered by Madhu Sudan) at MIT: 6.
^{841}⁄_{18}.405J Advanced Complexity Theory (Spring 2003). - [Tre1] A course on complexity theory (offered by Luca Trevisan) at UC, Berkeley: CS 278 - Computational Complexity (Fall 2002).
- [Tre2] A course on complexity theory (offered by Luca Trevisan) at UC, Berkeley: CS 278 - Computational Complexity (Fall 2004).
- [Vad] A course of complexity theory (offered by Salil Vadhan) at Harvard: CS221: Computational Complexity (Spring 2010).