Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Computability**- 15 meetings- Meeting 01 : Mon, Jul 29, 08:00 am-08:50 am
- Meeting 02 : Tue, Jul 30, 12:00 pm-12:50 pm
- Meeting 03 : Thu, Aug 01, 11:00 am-11:50 am
- Meeting 04 : Fri, Aug 02, 10:00 am-10:50 am
- Meeting 05 : Mon, Aug 05, 08:00 am-08:50 am
- Meeting 06 : Tue, Aug 06, 12:00 pm-12:50 pm
- Meeting 07 : Thu, Aug 08, 11:00 am-11:50 am
- Meeting 08 : Fri, Aug 09, 10:00 am-10:50 am
- Meeting 09 : Mon, Aug 12, 08:00 am-08:50 am
- Meeting 10 : Fri, Aug 23, 10:00 am-10:50 am
- Meeting 11 : Fri, Aug 23, 05:30 pm-06:45 pm
- Meeting 12 : Thu, Sep 12, 11:00 am-11:50 am
- Meeting 13 : Fri, Sep 13, 10:00 am-10:50 am
- Meeting 14 : Mon, Sep 16, 08:00 am-08:50 am
- Meeting 15 : Tue, Sep 17, 12:00 pm-12:50 pm

Administrative Announcements. References [Koz1] Exercises Reading Administrative Announcements.References: [Koz1] Introduction to Turing Machines. Informal definition. Formal definition. High level description of a Turing machine for an example language. References [Koz1] Exercises Reading Introduction to Turing Machines. Informal definition. Formal definition. High level description of a Turing machine for an example language.References: [Koz1] Full description of the TM for the example. Configurations, acceptance. Halting vs non halting. More examples. References [Koz 1] Exercises Reading Full description of the TM for the example. Configurations, acceptance. Halting vs non halting. More examples.References: [Koz 1] More examples. High level description of a TM for another non context-free language. Extensions: Two-way, multi-tape TMs etc. References [Koz 1] Exercises Reading More examples. High level description of a TM for another non context-free language. Extensions: Two-way, multi-tape TMs etc.References: [Koz 1] An encoding for TMs. Goedel numbering. Universal Turing machines. References [Koz 1] Exercises Reading An encoding for TMs. Goedel numbering. Universal Turing machines.References: [Koz 1] More examples of Recursive languages. Recursively enumerable languages. Halting and membership problems. References [Koz 1 ] Exercises Reading More examples of Recursive languages. Recursively enumerable languages. Halting and membership problems.References: [Koz 1 ] Non-recursive languages. Halting problem is non-recursive. Proof using Cantor's diagonalization. References Exercises Reading Non-recursive languages. Halting problem is non-recursive. Proof using Cantor's diagonalization.References: None Cantor's diagonalization. Halting on the null string. Example problems with TM encodings as input. References Exercises Reading Cantor's diagonalization. Halting on the null string. Example problems with TM encodings as input.References: None Notion of reductions. Non-recursive languages using reductions. References Exercises Reading Notion of reductions. Non-recursive languages using reductions.References: None Rice's theorem: Part 2. References Exercises Reading Rice's theorem: Part 2.References: None Notion of oracle Turing machines. References Exercises Reading Notion of oracle Turing machines.References: None Relativization. Turing reduction. References Exercises Reading Relativization. Turing reduction.References: None The definition of Arithmetic hierarchy. Characterization of AH using first order quantifiers (Arithmetic Hierarchy Theorm) References Exercises Reading The definition of Arithmetic hierarchy. Characterization of AH using first order quantifiers (Arithmetic Hierarchy Theorm)References: None Complete Languages in the Arithmetic hierarchy. References Exercises Reading Complete Languages in the Arithmetic hierarchy.References: None Complete problems for various levels of AH. References Exercises Reading Complete problems for various levels of AH.References: None **Theme 2 : Basics of Complexity Theory**- 23 meetings- Meeting 16 : Thu, Sep 19, 11:00 am-11:50 am
- Meeting 17 : Fri, Sep 20, 10:00 am-10:50 am
- Meeting 18 : Fri, Sep 20, 03:30 pm-04:40 pm
- Meeting 19 : Sat, Sep 21, 09:00 am-09:50 am
- Meeting 20 : Sat, Sep 21, 09:50 am-10:20 am
- Meeting 21 : Sat, Sep 21, 10:30 am-11:35 am
- Meeting 22 : Mon, Sep 23, 08:00 am-08:50 am
- Meeting 23 : Tue, Sep 24, 12:00 pm-12:50 pm
- Meeting 24 : Thu, Sep 26, 11:00 am-11:50 am
- Meeting 25 : Fri, Sep 27, 10:00 am-10:50 am
- Meeting 26 : Tue, Oct 01, 12:00 pm-12:50 pm
- Meeting 27 : Thu, Oct 03, 11:00 am-11:50 am
- Meeting 28 : Fri, Oct 04, 09:00 am-09:50 am
- Meeting 29 : Fri, Oct 04, 10:00 am-10:50 am
- Meeting 30 : Mon, Oct 07, 08:00 am-08:50 am
- Meeting 31 : Tue, Oct 08, 12:00 pm-12:50 pm
- Meeting 32 : Thu, Oct 10, 11:00 am-11:50 am
- Meeting 33 : Fri, Oct 11, 10:00 am-10:50 am
- Meeting 34 : Mon, Oct 14, 08:00 am-08:50 am
- Meeting 35 : Tue, Oct 15, 12:00 pm-12:50 pm
- Meeting 36 : Thu, Oct 17, 11:00 am-11:50 am
- Meeting 37 : Fri, Oct 18, 10:00 am-11:00 am
- Meeting 38 : Tue, Oct 22, 12:00 pm-12:50 pm

Non deterministic Turing Machines. Time complexity: Time bounded TMs. References [Koz2] Exercises Reading Non deterministic Turing Machines. Time complexity: Time bounded TMs.References: [Koz2] Time hierarchy theorem. References Exercises Reading Time hierarchy theorem.References: None Multi tape vs single tape machines. References Exercises Reading Multi tape vs single tape machines.References: None Space complexity. COPY is in DSPACE(log n). STCONN is in NSPACE(log n). References Exercises Reading Space complexity. COPY is in DSPACE(log n). STCONN is in NSPACE(log n).References: None Time vs Space. Configuration graph. Universal TM: simulating time and space bounded machines. References Exercises Reading Time vs Space. Configuration graph. Universal TM: simulating time and space bounded machines.References: None Time hierarchy theorem: proof via diagonalization. References Exercises Reading Time hierarchy theorem: proof via diagonalization.References: None Space hierarchy theorem. Concrete Complexity Classes. References Exercises Reading Space hierarchy theorem. Concrete Complexity Classes.References: None Relationship between L, NL, P, NP, PSPACE, NPSACE. Savitch's theorem. Notion of reductions. Robustness of the complexity classes. References Exercises Reading Relationship between L, NL, P, NP, PSPACE, NPSACE. Savitch's theorem. Notion of reductions. Robustness of the complexity classes.References: None The class NP: Guess and verify property. Quantifier characterization. NP completeness. References Exercises Reading The class NP: Guess and verify property. Quantifier characterization. NP completeness.References: None Cook-Levin theorem: SAT is NP complete. Circuit-SAT. Construction of a circuit from a t time bounded DTM. References Exercises Reading Cook-Levin theorem: SAT is NP complete. Circuit-SAT. Construction of a circuit from a t time bounded DTM.References: None Proof of Cook-Levin. Circuit SAT to SAT. Log-space many-one reductions. References Exercises Reading Proof of Cook-Levin. Circuit SAT to SAT. Log-space many-one reductions.References: None SAT to 3SAT. NP completeness of vertex cover, IndSet and Clique. References Exercises Reading SAT to 3SAT. NP completeness of vertex cover, IndSet and Clique.References: None Between NP and NP-C: Ladner's theorem. Proof. References Exercises Reading Between NP and NP-C: Ladner's theorem. Proof.References: None The polynomial time hierarchy: Quantifier based definition. Oracle based definition. Complete problems. References Exercises Reading The polynomial time hierarchy: Quantifier based definition. Oracle based definition. Complete problems.References: None No Lecture. References Exercises Reading No Lecture.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None Characterization of PH based on oracle TMs: Full proof. References Exercises Reading Characterization of PH based on oracle TMs: Full proof.References: None PSAPCE: QBF is complete for PSPACE. References Exercises Reading PSAPCE: QBF is complete for PSPACE.References: None The class NL. STCONN is complete for NL. NL=co-NL (Immermann-Szelepscenyi) References Exercises Reading The class NL. STCONN is complete for NL. NL=co-NL (Immermann-Szelepscenyi)References: None Immermann-Szelepscenyi: Proof. Padding arguments. References Exercises Reading Immermann-Szelepscenyi: Proof. Padding arguments.References: None Immerman Szelepcenyi References Exercises Reading Immerman SzelepcenyiReferences: None Padding Arguments. References Exercises Reading Padding Arguments.References: None Relativization: Baker-Gill-Solovay References Exercises Reading Relativization: Baker-Gill-SolovayReferences: None **Theme 3 : Randomness in computation and Counting Complexity**- 16 meetings- Meeting 39 : Tue, Oct 22, 05:00 pm-05:50 pm
- Meeting 40 : Tue, Oct 22, 05:50 pm-06:40 pm
- Meeting 41 : Thu, Oct 24, 11:00 am-11:50 am
- Meeting 42 : Fri, Oct 25, 10:00 am-10:50 am
- Meeting 43 : Fri, Oct 25, 03:30 pm-04:40 pm
- Meeting 44 : Mon, Oct 28, 08:00 am-08:50 am
- Meeting 45 : Tue, Oct 29, 12:00 pm-12:50 pm
- Meeting 46 : Thu, Oct 31, 11:00 am-11:50 am
- Meeting 47 : Fri, Nov 01, 10:00 am-10:50 am
- Meeting 48 : Mon, Nov 04, 08:00 am-08:50 am
- Meeting 49 : Tue, Nov 05, 12:00 pm-12:50 pm
- Meeting 50 : Tue, Nov 05, 05:00 pm-06:35 pm
- Meeting 51 : Thu, Nov 07, 11:00 am-11:50 am
- Meeting 52 : Fri, Nov 08, 10:00 am-10:50 am
- Meeting 53 : Fri, Nov 08, 03:30 pm-04:45 pm
- Meeting 54 : Mon, Nov 11, 08:00 am-08:50 am

Introduction to Counting Complexity. #P. Parsimonious reductions. Counting Satisfiying assignments. Counting Matchings. Permanent. Cycle covers. Many-one reductions. References Exercises Reading Introduction to Counting Complexity. #P. Parsimonious reductions. Counting Satisfiying assignments. Counting Matchings. Permanent. Cycle covers. Many-one reductions.References: None Properties of #P. References Exercises Reading Properties of #P.References: None Permanent is #P complete. References Exercises Reading Permanent is #P complete.References: None Permanent is #P complete (contd). Introduction to probabilistic computation. Error probability. One sided vs two sided. Classes RP, BPP and coRP. References Exercises Reading Permanent is #P complete (contd). Introduction to probabilistic computation. Error probability. One sided vs two sided. Classes RP, BPP and coRP.References: None References Exercises Reading References: None Relationship between RP, BP, PP and NP. Amplification of success probability for RP References Exercises Reading Relationship between RP, BP, PP and NP. Amplification of success probability for RPReferences: None Amplification of success probability for BPP. BPP vs PH. References Exercises Reading Amplification of success probability for BPP. BPP vs PH.References: None The class ZPP. Monte-Carlo vs Las Vegas. An example: Polynomial Identity Testing (ACIT). The BP operator. References Exercises Reading The class ZPP. Monte-Carlo vs Las Vegas. An example: Polynomial Identity Testing (ACIT). The BP operator.References: None BP operator (contd) References Exercises Reading BP operator (contd)References: None Parity-P. Properties of parity-P. References Exercises Reading Parity-P. Properties of parity-P.References: None Properties of parity-P (contd). PH vs PP: Toda's theorem. Statement. Can we isolate a witness: UP vs NP. Isolation lemma. Isolation of a witness: Valiant-Vazirani Isolation Lemma. References Exercises Reading Properties of parity-P (contd). PH vs PP: Toda's theorem. Statement. Can we isolate a witness: UP vs NP. Isolation lemma. Isolation of a witness: Valiant-Vazirani Isolation Lemma.References: None Valiant-Vazirani Isolation Lemma. References Exercises Reading Valiant-Vazirani Isolation Lemma.References: None Toda's theorem: proof. References Exercises Reading Toda's theorem: proof.References: None Proof systems: Definition and examples. Main results. References Exercises Reading Proof systems: Definition and examples. Main results.References: None Probabilistically Checkable proofs. PCP vs NP. Main results. References Exercises Reading Probabilistically Checkable proofs. PCP vs NP. Main results.References: None GapCSP and PCP. Application to hardness of approximation. References Exercises Reading GapCSP and PCP. Application to hardness of approximation.References: None