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**- 19 meetings- Meeting 01 : Mon, Aug 03, 08:00 am-08:50 am
- Meeting 02 : Tue, Aug 04, 12:00 pm-12:50 pm
- Meeting 03 : Thu, Aug 06, 11:00 am-11:50 am
- Meeting 04 : Fri, Aug 07, 10:00 am-10:50 am
- Meeting 05 : Sat, Aug 08, 09:00 am-12:00 pm
- Meeting 06 : Mon, Aug 10, 08:00 am-08:50 am
- Meeting 07 : Tue, Aug 11, 12:00 pm-12:50 pm
- Meeting 08 : Thu, Aug 13, 11:00 am-11:50 am
- Meeting 09 : Fri, Aug 14, 10:00 am-10:50 am
- Meeting 10 : Mon, Aug 17, 08:00 am-08:50 am
- Meeting 11 : Tue, Aug 18, 12:00 pm-12:50 pm
- Meeting 12 : Thu, Aug 20, 11:00 am-11:50 am
- Meeting 13 : Fri, Aug 21, 10:00 am-10:50 am
- Meeting 14 : Mon, Aug 24, 08:00 am-08:50 am
- Meeting 15 : Tue, Aug 25, 12:00 pm-12:50 pm
- Meeting 16 : Mon, Aug 31, 08:00 am-08:50 am
- Meeting 17 : Tue, Sep 01, 12:00 pm-12:50 pm
- Meeting 18 : Tue, Sep 01, 04:45 pm-06:15 pm
- Meeting 19 : Wed, Nov 11, 10:00 am-12:00 pm

Administrative Announcements. Review of Turing machines. Definitions. Recursive and Recursively enumerable languages. References Exercises Reading Administrative Announcements. Review of Turing machines. Definitions. Recursive and Recursively enumerable languages.References: None The Turing Model of Computation. Notion of Configurations and moves. References [K1Book] Exercises Reading The Turing Model of Computation. Notion of Configurations and moves.References: [K1Book] Languages accepted by Turing Machines. Decidability and Semi-decidability. Recursive languages. Recursively enumerable languages. References Exercises Reading Languages accepted by Turing Machines. Decidability and Semi-decidability. Recursive languages. Recursively enumerable languages.References: None Closure properties of RE sets. Equivalent models: Multitape TMs. Universal Turing machines. References [K1 Book] Exercises Reading Closure properties of RE sets. Equivalent models: Multitape TMs. Universal Turing machines.References: [K1 Book] Diagonalization- Cantor's argument. The Halting Problem (HP) is non-recursive. Undecidability of the MP - Membership Problem. Notion of Reductions. References [K1 Book] Exercises Reading Diagonalization- Cantor's argument. The Halting Problem (HP) is non-recursive. Undecidability of the MP - Membership Problem. Notion of Reductions.References: [K1 Book] More problems over Turing machines. Decidable and undecidable questions. Testing decidability of the languages of the given TM. References [K1 Book] Exercises Reading More problems over Turing machines. Decidable and undecidable questions. Testing decidability of the languages of the given TM.References: [K1 Book] Showing undecidability of the following tasks: Testing Regularity, Testing Context-freeness. Rice's Theorem, part - 1 References [K1 Book] Exercises Reading Showing undecidability of the following tasks: Testing Regularity, Testing Context-freeness. Rice's Theorem, part - 1References: [K1 Book] Rices Theorem Part - 2. Applications of Rice's theorem. References Exercises Reading Rices Theorem Part - 2. Applications of Rice's theorem.References: None More non recursive and non-r.e languages. Relative computation. References Exercises Reading More non recursive and non-r.e languages. Relative computation.References: None Oracle Turing machines. Building above r.e. sets. The arithmetic Hierarchy. References Exercises Reading Oracle Turing machines. Building above r.e. sets. The arithmetic Hierarchy.References: None Characterization of the Arithmetic Hierarchy. References <a href="http://www.cse.buffalo.edu/~regan/cse596/AH.pdf"> Notes </a> by Ken Regan. Exercises Reading Characterization of the Arithmetic Hierarchy.References: Notes by Ken Regan. Characterization of AH (contd) References Exercises Reading Characterization of AH (contd)References: None Complete problems for AH. References Exercises Reading Complete problems for AH.References: None Complete problems for AH. Post's problem. Post's theorem. References Exercises Reading Complete problems for AH. Post's problem. Post's theorem.References: None Posts theorem (Proof.) References Exercises Reading Posts theorem (Proof.)References: None Post's theorem (contd). References Exercises Reading Post's theorem (contd).References: None Freidgut Muchnik theorem (without proof). Analytical hierarchy (definition only). Resource measures on computation. Blums axioms. References Exercises Reading Freidgut Muchnik theorem (without proof). Analytical hierarchy (definition only). Resource measures on computation. Blums axioms.References: None no lecture. References Exercises Reading no lecture.References: None Goedel's incompleteness theorem (Optional Lecture) References Exercises Reading Goedel's incompleteness theorem (Optional Lecture)References: None **Theme 2 : Basic Complexity Theory: Time and Space**- 21 meetings- Meeting 20 : Thu, Sep 03, 11:00 am-11:50 am
- Meeting 21 : Fri, Sep 04, 10:00 am-10:50 am
- Meeting 22 : Tue, Sep 08, 12:00 pm-12:50 pm
- Meeting 23 : Thu, Sep 10, 11:00 am-11:50 am
- Meeting 24 : Fri, Sep 11, 10:00 am-10:50 am
- Meeting 25 : Sat, Sep 12, 09:00 am-12:00 pm
- Meeting 26 : Mon, Sep 14, 08:00 am-08:50 am
- Meeting 27 : Tue, Sep 15, 12:00 pm-12:50 pm
- Meeting 28 : Fri, Sep 18, 10:00 am-10:50 am
- Meeting 29 : Mon, Sep 21, 08:00 am-08:50 am
- Meeting 30 : Mon, Sep 21, 05:00 pm-06:30 pm
- Meeting 31 : Tue, Sep 22, 12:00 pm-12:50 pm
- Meeting 32 : Thu, Sep 24, 02:00 pm-03:45 pm
- Meeting 33 : Fri, Sep 25, 10:00 am-10:50 am
- Meeting 34 : Mon, Oct 19, 08:00 am-08:50 am
- Meeting 35 : Tue, Oct 20, 12:00 pm-12:50 pm
- Meeting 36 : Mon, Oct 26, 08:00 am-08:50 am
- Meeting 37 : Tue, Oct 27, 12:00 pm-12:50 pm
- Meeting 38 : Thu, Oct 29, 11:00 am-11:50 am
- Meeting 39 : Fri, Oct 30, 10:00 am-10:50 am
- Meeting 40 : Mon, Nov 02, 08:00 am-08:50 am

Resource bounded computation. Resources required by Regular Languages and context free languages. Notion of complexity Measure. Blum's axioms. References [K2] Exercises Reading Resource bounded computation. Resources required by Regular Languages and context free languages. Notion of complexity Measure. Blum's axioms.References: [K2] Blum's axioms. Gap theorem. Speed up theorem. Time and Space constructible functions. Linear Speed up theorems. References [K2] book. See the chapter on Abstract Complexity. Exercises Reading Blum's axioms. Gap theorem. Speed up theorem. Time and Space constructible functions. Linear Speed up theorems.References: [K2] book. See the chapter on Abstract Complexity. Linear Speed up theorems. References Your class notes!! Exercises Reading Linear Speed up theorems.References: Your class notes!! Hierarchy theorems: Space hierarchy theorem, proof. References Exercises Reading Hierarchy theorems: Space hierarchy theorem, proof.References: None Time hierarchy theorem. Proof. First Lower bounds: Crossing sequence arguments. References [MB Notes]. Exercises Reading Time hierarchy theorem. Proof. First Lower bounds: Crossing sequence arguments.References: [MB Notes]. First Lower bounds: Crossing sequence arguments. DSpace(o(loglog n))= DSpace(O(1)). The complexity classes EXP, E, and P, L (DLOG). Positioning of computational problems CLIQUE, SAT and REACH. CLIQUE is in EXP, SAT is in E, REACH is in P, DF-CONN is in L. EXACT-CLIQUE vs CLIQUE: efficient verifiability of solutions. Non-deterministic Turing machines. Non-deterministic Time and Space. References Your class notes!! Exercises Reading First Lower bounds: Crossing sequence arguments. DSpace(o(loglog n))= DSpace(O(1)). The complexity classes EXP, E, and P, L (DLOG). Positioning of computational problems CLIQUE, SAT and REACH. CLIQUE is in EXP, SAT is in E, REACH is in P, DF-CONN is in L. EXACT-CLIQUE vs CLIQUE: efficient verifiability of solutions. Non-deterministic Turing machines. Non-deterministic Time and Space.References: Your class notes!! Non-deterministic Time and Space. The classes NP and NL. CLIQUE and SAT are in NP. References Your class notes!! Exercises Reading Non-deterministic Time and Space. The classes NP and NL. CLIQUE and SAT are in NP.References: Your class notes!! CLIQUE is in NP. REACH is in NL. References Your class notes!! Exercises Reading CLIQUE is in NP. REACH is in NL.References: Your class notes!! Relation to determinisitic counterparts: L subseteq NL subseteq P subseteq NP subseteq EXP. Characterization of classes: Notion of hardness and completeness. References [MB Notes] Exercises Reading Relation to determinisitic counterparts: L subseteq NL subseteq P subseteq NP subseteq EXP. Characterization of classes: Notion of hardness and completeness.References: [MB Notes] Notions of reductions and completeness. log-space reductions. REACH is NL complete under log-space reductions. References [MB Notes]. Exercises Reading Notions of reductions and completeness. log-space reductions. REACH is NL complete under log-space reductions.References: [MB Notes]. Closure properties of NL. Union, intersection and Complement. NL is closed under complement: Immermann-Szelepscenyi theorem. References [MB Notes]. Also see [K2]. Exercises Reading Closure properties of NL. Union, intersection and Complement. NL is closed under complement: Immermann-Szelepscenyi theorem.References: [MB Notes]. Also see [K2]. Time Complexity Classes, P, NP, EXP. Padding Arguments. P = NP implies NEXP = EXP. The class NP. Properties: closure under union and intersection. Boolean Circuits. References [MB Notes]. Exercises Reading Time Complexity Classes, P, NP, EXP. Padding Arguments. P = NP implies NEXP = EXP. The class NP. Properties: closure under union and intersection. Boolean Circuits.References: [MB Notes]. Boolean circuits. Circuit Valuation Problem (CVP). CVP is P-Complete under log-space reductions. Circuit Satisfiability (CSAT). CSAT is NP-complete under log-space reductions. References Exercises Reading Boolean circuits. Circuit Valuation Problem (CVP). CVP is P-Complete under log-space reductions. Circuit Satisfiability (CSAT). CSAT is NP-complete under log-space reductions.References: None More NP complete problems: Vertex Cover, Clique. Landscape of complexity classes. References Exercises Reading More NP complete problems: Vertex Cover, Clique. Landscape of complexity classes.References: None Ladner's theorem introduction and proof. References [MB Notes] Exercises Reading See <a href="http://oldblog.computationalcomplexity.org/media/ladner.pdf"> Two proofs of Ladner's theorem</a> by Lance Fortnow. Ladner's theorem introduction and proof.References: [MB Notes] Reading: See Two proofs of Ladner's theorem by Lance Fortnow. Ladner's theorem: proof References [MBNotes] Exercises Reading Ladner's theorem: proofReferences: [MBNotes] Generalizations of NP. 1) Based alternating quantifiers. Definition of Polynomial Hierarchy. Examples. Circuit Minimization Problem, Formula Isomorphism Problem. 2) Characterization of PH in terms of relativizations. References [MBNotes] Exercises Reading There are several natural complete problems for various levels of PH. See <a href="http://ovid.cs.depaul.edu/documents/phcom.ps"> a compendium </a> of such problems maintained by Schaefer and Umans. Generalizations of NP. 1) Based alternating quantifiers. Definition of Polynomial Hierarchy. Examples. Circuit Minimization Problem, Formula Isomorphism Problem. 2) Characterization of PH in terms of relativizations.References: [MBNotes] Reading: There are several natural complete problems for various levels of PH. See a compendium of such problems maintained by Schaefer and Umans. Quantified Boolean Formulas. Completeness for PH and PSPACE. References Exercises Reading Quantified Boolean Formulas. Completeness for PH and PSPACE.References: None PSPACE completeness of QBF. Alternating Turing machines. Relations to PSPACE and PH. References Exercises Reading PSPACE completeness of QBF. Alternating Turing machines. Relations to PSPACE and PH.References: None Oracle TMs, Turing reduction. Diagonalization and its limitation against Relativization: Baker-Gill-Solovay theorem. Proof of Baker-Gill-Solovay. References Exercises Reading Oracle TMs, Turing reduction. Diagonalization and its limitation against Relativization: Baker-Gill-Solovay theorem. Proof of Baker-Gill-Solovay.References: None Proof of Baker Gill Solovay (contd). Mahaney's theorem: Sparse sets cannot be NP complete unless P = NP, proof sketch. References For BGS see [K2]. For Mahaney's theorem see [MB Notes]. Also see the <a href="https://courses.engr.illinois.edu/cs579/resources/cai-mahaney.pdf"> notes </a> by Jin Yi Cai for a simplified presentation. Exercises Reading Proof of Baker Gill Solovay (contd). Mahaney's theorem: Sparse sets cannot be NP complete unless P = NP, proof sketch.References: For BGS see [K2]. For Mahaney's theorem see [MB Notes]. Also see the notes by Jin Yi Cai for a simplified presentation. **Theme 3 : Counting and Randomization**- 8 meetings- Meeting 41 : Tue, Nov 03, 12:00 pm-12:50 pm
- Meeting 42 : Thu, Nov 05, 11:00 am-11:50 am
- Meeting 43 : Fri, Nov 06, 10:00 am-10:50 am
- Meeting 44 : Mon, Nov 09, 08:00 am-08:50 am
- Meeting 45 : Tue, Nov 10, 12:00 pm-12:50 pm
- Meeting 46 : Thu, Nov 12, 11:00 am-11:50 am
- Meeting 47 : Fri, Nov 13, 10:00 am-10:50 am
- Meeting 48 : Mon, Nov 16, 08:00 am-08:50 am

Completion of Mahaney's theorem. Randomization. Probabilistic Turing machines. Probabilistic Complexity Classes: RP, BPP and PP. References [MB Notes] and [K2 Book] Exercises Reading Completion of Mahaney's theorem. Randomization. Probabilistic Turing machines. Probabilistic Complexity Classes: RP, BPP and PP.References: [MB Notes] and [K2 Book] Property of probabilistic classes: Closure properties. Representing polynomials at the input: Monomial representation, Arithmetic circuits. References [MB Notes] and [K2 Book] Exercises Reading Property of probabilistic classes: Closure properties. Representing polynomials at the input: Monomial representation, Arithmetic circuits.References: [MB Notes] and [K2 Book] The polynomial Identity Testing Problem. Schwartz-Zippel Lemma: PIT is in co-RP. References [K2 Book] and [MB notes] Exercises Reading The polynomial Identity Testing Problem. Schwartz-Zippel Lemma: PIT is in co-RP.References: [K2 Book] and [MB notes] Amplification of success probability. BPP in Sigma_2 cap Pi_2. References [K2 Book], Lecture 13. Also see <a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture11.pdf"> Notes </a> by Jayalal Sarma. Exercises Reading Amplification of success probability. BPP in Sigma_2 cap Pi_2.References: [K2 Book], Lecture 13. Also see Notes by Jayalal Sarma. Complexity of Counting. Counting solutions: Number of Satisfying assignments, cycles in a graph. Counting accepting paths in an NTM. Reductions: parsimonious and many-one. References [MB Notes] Exercises Reading Complexity of Counting. Counting solutions: Number of Satisfying assignments, cycles in a graph. Counting accepting paths in an NTM. Reductions: parsimonious and many-one.References: [MB Notes] Counting problems where the corresponding decision version is in P: Counting Perfect matchings in a bipartite graphs. References Exercises Reading Counting problems where the corresponding decision version is in P: Counting Perfect matchings in a bipartite graphs.References: None Generalization of counting perfect matchings: permanent of a matrix. Permanent is #P complete under many-one reductions. References Exercises Reading Generalization of counting perfect matchings: permanent of a matrix. Permanent is #P complete under many-one reductions.References: None Permanent is #P complete References Exercises Reading Permanent is #P completeReferences: None **Theme 4 : Evaluation Meetings**- 3 meetings- Meeting 49 : Mon, Sep 07, 08:00 am-08:50 am
- Meeting 50 : Mon, Oct 12, 08:00 am-08:50 am
- Meeting 51 : Wed, Nov 18, 01:00 pm-04:00 pm

To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None End Semester Exam References Exercises Reading End Semester ExamReferences: None **Theme 5 : No Lecture**- 10 meetings- Meeting 52 : Mon, Sep 28, 08:00 am-08:50 am
- Meeting 53 : Tue, Sep 29, 12:00 pm-12:50 pm
- Meeting 54 : Thu, Oct 01, 11:00 am-11:50 am
- Meeting 55 : Mon, Oct 05, 08:00 am-08:50 am
- Meeting 56 : Tue, Oct 06, 12:00 pm-12:50 pm
- Meeting 57 : Thu, Oct 08, 11:00 am-11:50 am
- Meeting 58 : Fri, Oct 09, 10:00 am-10:50 am
- Meeting 59 : Tue, Oct 13, 12:00 pm-12:50 pm
- Meeting 60 : Thu, Oct 15, 11:00 am-11:50 am
- Meeting 61 : Fri, Oct 16, 10:00 am-10:50 am

Post's Theorem (contd) References Exercises Reading Post's Theorem (contd)References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None