| 15th Jan, 2008 | Discussed the syllabus and goal of the course, Introduce Turing machines model of computation. | |
| 17th Jan, 2008 | More Turing machine examples, undecidable sets, Rices theorem | |
| 22nd Jan, 2008 | Deterministic time and space complexity classes introduction | |
| 24th Jan, 2008 | Examples and relation among determinsitic clases, Prereq test | |
| 29th Jan, 2008 | Nondeterministic clases and relations between deterministic and nondeterministic classes. | |
| 31st Jan, 2008 | Savitch's theorem, Deterministic time and space hierarchy theorems. | |
| 05th Feb, 2008 | Nondeterministic hierarchy theorem. Co classes. | |
| 07th Feb, 2008 | Reachability, NLOG = coNLOG. | |
| 12th Feb, 2008 | Reductions and Completeness: Cook-Levin theorem | |
| 14th Feb, 2008 | CNFSAT -> 3SAT -> IndSet. Complete picture of relations and completeness for complexity classes so far. | |
| 19th Feb, 2008 | QSAT is PSPACE complete | |
| 21th Feb, 2008 | Boolean circuits, Problems in PPoly, discussed homeworks | |
| 26th Feb, 2008 | Small circuit for Reachability, P in PPoly, CVP is P complete | |
| 28th Feb, 2008 | Lower bounds. Shannon's lower bound, (2n-4) lower bound for Threshold functions. | |
| 04th March, 2008 | PSPACE not in fixed Polynomial size circuits, Randomization: Polynomial Identity Testing and Schwartz-Zippel lemma | |
| 06th March, 2008 | Randomized Algorithm for Bipartite Perfect Matching, Probabilistic TM, BPP, RP definitions and relations | |
| 11th March, 2008 | Basic Probability theory and Chernoff bounds | |
| 13th March, 2008 | Error reduction for BPP, and BPP in PPoly | |
| 18th March, 2008 | Spring Break | |
| 20th March, 2008 | Spring Break | |
| 25th March, 2008 | Finite State Markov Chain Fundamentals | |
| 27th March, 2008 | UndREACH in RL | |
| 01st April, 2008 | Pairwise independence and 2-universality | |
| 03rd April, 2008 | Nisan's generator for space bounded computations | |
| 08th April, 2008 | Nisan's generator Cont. | |
| 03rd April, 2008 | Nisan's generator for reducing error in randomized computations |