- Meeting 01 : Mon, Jul 25, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Introduction to computability and its origins from Hilbert's program. Overview of the course. Administrative announcements.
- Meeting 02 : Tue, Jul 26, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Turing machines: formal definition. A detailed example. Notion of configurations.
- Meeting 03 : Thu, Jul 28, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Notion of configurations. Transition relation for configurations. Examples of TMs.
- Meeting 04 : Fri, Jul 29, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
More details of the example. Variations of TMs: k-tape TMs.
- Meeting 05 : Mon, Aug 01, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
k-tape TM to 1-tape TMs. State level description. Closure properties of RE and REC.
- Meeting 06 : Tue, Aug 02, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
More closure properties of RE and REC. Other variants of TMS: 2-way infinite tapes, two stack machines. Enumerating machines.
- Meeting 07 : Thu, Aug 04, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Enumerating machines (contd). Universal Turing Machines. HP and MP
- Meeting 08 : Fri, Aug 05, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Cantor's diagonalization for uncountability of 2^N. Proving undecidability of HP and MP.
- Meeting 09 : Thu, Aug 11, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Undecidability of HP and MP. Cantor's diagonalization.
- Meeting 10 : Fri, Aug 12, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
More questions on TMS.
- Meeting 11 : Tue, Aug 16, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
More questions on TMS (contd). FIN and its complement are not RE.
- Meeting 12 : Thu, Aug 18, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Rice's theorem
- Meeting 13 : Fri, Aug 19, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Rice's theorem (contd)
- Meeting 14 : Mon, Aug 22, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Overview of computability. Introduction to resource-bounded computation.
- Meeting 15 : Tue, Aug 23, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Quantifier characterization of RE sets. Arithmetic hierarchy.
- Meeting 16 : Thu, Aug 25, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Time and space as resources. Linear Speedup
- Meeting 17 : Fri, Aug 26, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Linear speedup (contd). Definition of complexity classes, DTime and NTime. Space bounded computations. Examples: STCON.
- Meeting 18 : Mon, Aug 29, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Short Quiz - 1
- Meeting 19 : Tue, Aug 30, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Dtime(), NTime(), Dspace(), NSpace(). Relationships between these classes.
- Meeting 20 : Thu, Sep 01, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Nspace vs Dspace: Savitch's theorem. Time and space- constructible functions. Time hierarchy theorem
References: | For hierarchy theorem: Scribe notes by Markus Blaeser (shared on google drive)
|
- Meeting 21 : Fri, Sep 02, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Space hierarchy theorem
References: | Scribe notes by Markus Blaeser (shared on google drive)
|
- Meeting 22 : Mon, Sep 05, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Single tape vs multitape. A separation using crossing sequences.
- Meeting 23 : Tue, Sep 06, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Limitations of hierarchy theorems. Concrete complexity classes.
References: | Blaeser notes.
|
- Meeting 24 : Thu, Sep 08, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Concrete complexity classes: P, NP, DLOG, NLOG, PSPACE, NPSPACE, E, EXP etc.
- Meeting 25 : Fri, Sep 09, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Characterizing complexity classes. A quantifier based characterization of NP.
- Meeting 26 : Mon, Sep 12, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Example languages in NP. PRIMES in NP.
- Meeting 27 : Tue, Sep 13, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Cook-Levin theorem.
- Meeting 28 : Thu, Sep 15, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Proof of Cook-Levin (contd)
- Meeting 29 : Fri, Sep 16, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Cook-Levin theorem (contd)
- Meeting 30 : Mon, Sep 19, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
More NP-complete problems.
- Meeting 31 : Tue, Sep 20, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
More NP-complete problems
- Meeting 32 : Thu, Sep 22, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
More NP-completeness
- Meeting 33 : Fri, Sep 23, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
No Lecture.
- Meeting 34 : Mon, Sep 26, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
The Class coNP. Relativized computation.
- Meeting 35 : Tue, Sep 27, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
The polynomial time hierarchy. Examples. THe polynomial time Hierarchy theorem
- Meeting 36 : Thu, Sep 29, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
THe polynomial time Hierarchy theorem
- Meeting 37 : Fri, Sep 30, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
THe polynomial time Hierarchy theorem.
- Meeting 38 : Thu, Oct 06, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Characterization of PSPACE.
- Meeting 39 : Fri, Oct 07, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Log space bounded computation. DLOG and NL. Directed Forest reachability is in DLOG.
- Meeting 40 : Mon, Oct 10, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
The class NL. NL completeness.
- Meeting 41 : Tue, Oct 11, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
NL = coNL
- Meeting 42 : Thu, Oct 13, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
NL = co-NL
- Meeting 43 : Fri, Oct 14, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Circuit Model of computation. Boolean circuits. P -completeness. The class P/poly.
- Meeting 44 : Mon, Oct 17, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Boolean circuits. Karp Lipton Theorem.
- Meeting 45 : Tue, Oct 18, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Karp Lipton - contd. Classes NC^i and AC^i
- Meeting 46 : Thu, Oct 20, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Examples of Boolean circuits.
- Meeting 47 : Fri, Oct 21, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Boolean Circuits. Parity is not in AC0
- Meeting 48 : Tue, Oct 25, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Parity is not in AC0 (contd). Introduction to probabilistic computation.
- Meeting 49 : Thu, Oct 27, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Probabilistic computation - 2. PP, BPP, and RP
- Meeting 50 : Fri, Oct 28, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Probabilistic computation - 3. Success probability amplification. Examples. Schwartz-Zippel.
- Meeting 51 : Sun, Oct 30, 10:05 am-11:10 am
References | |
Exercises | |
Reading | |
Examples. Schwartz-Zippel. Overview of complexity theory research.
- Meeting 52 : Mon, Oct 31, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Introduction to Counting. #P and FP definitions. Counting Matchings and the permanent. Valiant's theorem: #P completeness of permanent.
- Meeting 53 : Tue, Nov 01, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Notion of reductions. Valiants theorem. Permanent is #P complete.
- Meeting 54 : Thu, Nov 03, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Valiant's theorem (contd)
- Meeting 55 : Fri, Nov 04, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Concluding remarks.