| 11th Jan, 2010 | Sylabus; Introduction to Complexity Theory (Vinod Variyam). |
| 13th Jan, 2010 | Model of computation: Turing machine and Examples (Raghu Tewari) |
| 15th Jan, 2010 | Robustness of TMs: tape-symbol reduction, tape reduction, Universal TM (Raghu Tewari). |
| 18th Jan, 2010 | MLK Day: UNL Holiday |
| 20th Jan, 2010 | Complexity classes P, NP, EXP and examples (Raghu Tewari). |
| 22nd Jan, 2010 | Equaivalence of definitions for NP. Reductions (Derrick Stolee). |
| 25th Jan, 2010 | Cook-Levin theorem, NP complete examples: 3SAT, INDSET (Derrick Stolee). |
| 27th Jan, 2010 | Selfreducibility of SAT and search vs decision, padding technique (Vinod Variyam) |
| 29th Jan, 2010 | Time hierarchy theorems (Vinod Variyam). |
| 01st Feb, 2010 | Time hierarchy theorems cont. (Vinod Variyam) |
| 03rd Feb, 2010 | Ladners theorem, oracles, space complexity classes. (Derrick Stolee) |
| 05th Feb, 2010 | Space complexity classes introduction and basic inclusions, QBF Pspace complete. (Derrick Stolee) |
| 08th Feb, 2010 | Space hierarchy, NL-completeness, Savitch's theorem (Derrick Stolee) |
| 10th Feb, 2010 | Immerman Szelepcenyi theorem: NL is closed under complement (Derrick Stolee). |
| 12th Feb, 2010 | Circuit Complexity: P \in P/poly; CVP P-complete, uniform circuits (Vinod Variyam). |
| 15th Feb, 2010 | Shannon lower bound, EXPSPACE not in P/ply, exponential upper bound (Vinod Variyam). |
| 17th Feb, 2010 | Ckt. hierarchy, AC, NC and more (Vinod Variyam). |
| 19th Feb, 2010 | Polynomial Hierarchy, completeness and properties (Derrick Stolee). |
| 22nd Feb, 2010 | Polynomial Hierarchy using ATM, AP=PSPACE, TimeSpace tradeoffs (Derrick Stolee). |
| 24th Feb, 2010 | Circuits and PH. Karp-Lipton theorem (Vinod Variyam). |
| 26th Feb, 2010 | Mayers Theorem, circuit lower bounds in PH (Vinod Variyam). |
| 01st Mar, 2010 | Probabilistic Computation, BPP, RP, coRP, ZPP (Derrick Stolee). |
| 03rd Mar, 2010 | Examples of Randomized Algorithms: KthElement, Polynomial Identity, Perfect Matchings in Bipartite Graphs (Derrick Stolee). |
| 05th Mar, 2010 | Robustness of Probabilistic Computation, BPP in P/poly (Derrick Stolee). |
| 08th Mar, 2010 | Sipser-Gacs Theorem (Derrick Stolee). |
| 10th Mar, 2010 | Review of topics so far (Vinod Variyam) |
| 12th Mar, 2010 | Advanced Topics: A glimpse (Vinod Variyam) |
| 15th Mar, 2010 | Spring Break |
| 17th Mar, 2010 | Spring Break |
| 19th Mar, 2010 | Spring Break |
| 22nd Mar, 2010 | Decision Tree Complexity (Vinod Variyam) |
| 24th Mar, 2010 | Decision Tree Complexity (Vinod Variyam) |
| 26th Mar, 2010 | Communication Complexity (Derrick Stolee) |
| 29th Mar, 2010 | Communication Complexity (Derrick Stolee) |
| 31st Mar, 2010 | Communication Complexity (Derrick Stolee) |
| 02nd Apr, 2010 | Communication Complexity (Derrick Stolee) |
| 05th Apr, 2010 | Circuit Complexity: Switching lemma and Parity lower bound (Vinod Variyam) |
| 07th Apr, 2010 | Switching lemma and Parity lower bound (Vinod Variyam) |
| 09th Apr, 2010 | Razborov-Smolensky: Parity not in ACC0(3) (Vinod Variyam) |