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 : Turing Machines and Computability**- 22 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 : Tue, Aug 13, 12:00 pm-12:50 pm
- Meeting 11 : Thu, Aug 15, 11:00 am-11:50 am
- Meeting 12 : Fri, Aug 16, 10:00 am-10:50 am
- Meeting 13 : Mon, Aug 19, 08:00 am-08:50 am
- Meeting 14 : Tue, Aug 20, 12:00 pm-12:50 pm
- Meeting 15 : Thu, Aug 22, 11:00 am-11:50 am
- Meeting 16 : Fri, Aug 23, 10:00 am-10:50 am
- Meeting 17 : Mon, Aug 26, 08:00 am-08:50 am
- Meeting 18 : Tue, Aug 27, 12:00 pm-12:50 pm
- Meeting 19 : Thu, Aug 29, 11:00 am-11:50 am
- Meeting 20 : Fri, Aug 30, 10:00 am-10:50 am
- Meeting 21 : Tue, Sep 03, 12:00 pm-12:50 pm
- Meeting 22 : Thu, Sep 05, 11:00 am-11:50 am

Administrative announcements. Hilbert's program. Turing's model of computation, Church-Turing thesis. References Chapter 1 of [BarryCoop] Exercises Reading <a href="http://plato.stanford.edu/entries/church-turing/"> Church-Turing thesis </a> <br> <a href="http://plato.stanford.edu/entries/hilbert-program/"> Hilbert's program </a> Administrative announcements. Hilbert's program. Turing's model of computation, Church-Turing thesis.References: Chapter 1 of [BarryCoop] Reading: Church-Turing thesis

Hilbert's programQuick revision of models of computation: DFA and NFA Proving non-computability for DFAs: pumping lemma. Definition of a Turing machine. References [K1 Book]: taken from various chapters. Exercises Reading Read about Pushdown Automata, Pumping Lemma for Context Free Languages. Quick revision of models of computation: DFA and NFA Proving non-computability for DFAs: pumping lemma. Definition of a Turing machine.References: [K1 Book]: taken from various chapters. Reading: Read about Pushdown Automata, Pumping Lemma for Context Free Languages. The Turing Model of Computation. Notion of Configurations and moves. Languages accepted by Turing Machines. Decidability and Semi-decidability. References Lectures 28, 29 in [K1 book]. Exercises Reading The Turing Model of Computation. Notion of Configurations and moves. Languages accepted by Turing Machines. Decidability and Semi-decidability.References: Lectures 28, 29 in [K1 book]. Diophantine sets: an example of r.e. languages. Other equivalent models for TM (2-way infinite models, multi tape machines). Tape reduction. Universal Turing Machines and encodings of TMs. References Lecture 31 in [K1 book]. Exercises Reading We have seen that diophantine sets are r.e. For a more detailed exposition and statement of Matiyasevich's theorem see the expository article: <a href="http://www.logicmatters.net/resources/pdfs/MRDP.pdf"> The MRDP Theorem </a> Diophantine sets: an example of r.e. languages. Other equivalent models for TM (2-way infinite models, multi tape machines). Tape reduction. Universal Turing Machines and encodings of TMs.References: Lecture 31 in [K1 book]. Reading: We have seen that diophantine sets are r.e. For a more detailed exposition and statement of Matiyasevich's theorem see the expository article: The MRDP Theorem Diagonalization- Cantor's argument. Decidability and Semi-decidability. Undecidability of the Halting Problem (HP). References Lecture 31 in [K1 book] Exercises Reading Diagonalization- Cantor's argument. Decidability and Semi-decidability. Undecidability of the Halting Problem (HP).References: Lecture 31 in [K1 book] Undecidability of the MP - Membership Problem. Notion of Reductions. Showing undecidability of the following tasks. Testing Regularity, Testing Context-freeness, Testing decidability of the languages of the given TM. References [K1 Book] Exercises Reading Undecidability of the MP - Membership Problem. Notion of Reductions. Showing undecidability of the following tasks. Testing Regularity, Testing Context-freeness, Testing decidability of the languages of the given TM.References: [K1 Book] Rice's theorem. Infinitely many undecidable sets Rice's theorem I - All nontrivial properties of semidecidable sets are undecidable. References Chapter 34 of [K1 Book] Exercises Reading Rice's theorem. Infinitely many undecidable sets Rice's theorem I - All nontrivial properties of semidecidable sets are undecidable.References: Chapter 34 of [K1 Book] No Lecture-Id-ul-Fitr. <! Landscape of undecidable sets, Semidecidable and Co-semidecidable sets. Rice's Second theorem- statement and applications.> References Exercises Reading No Lecture-Id-ul-Fitr.References: None Completing the proof of Rice's Theorem-I. Rice's theorem II - No non-monotone property of SD sets is semi-decidable. Proof References [K1 Book] Exercises Reading Completing the proof of Rice's Theorem-I. Rice's theorem II - No non-monotone property of SD sets is semi-decidable. ProofReferences: [K1 Book] Applications of Rice's thm: FIN is neither in SD nor in CoSD. Relative Computation. Oracle Turing Machines. Relative Decidability and Turing Reductions. References [K1 Book] Exercises Reading Applications of Rice's thm: FIN is neither in SD nor in CoSD. Relative Computation. Oracle Turing Machines. Relative Decidability and Turing Reductions.References: [K1 Book] No Lecture: Independence Day. References Exercises Reading No Lecture: Independence Day.References: None Relative Computation. Oracle Turing Machines. Relative Decidability and Turing Reductions. Relative Semi-decidability. Comparison with many-one reductions. Landscape outside semi-decidables : Arithmetic hierarchy of languages. Sigma, Pi and Delta. The structure of the hierarchy. References [K1 book] and [K2 book] Exercises Reading Relative Computation. Oracle Turing Machines. Relative Decidability and Turing Reductions. Relative Semi-decidability. Comparison with many-one reductions. Landscape outside semi-decidables : Arithmetic hierarchy of languages. Sigma, Pi and Delta. The structure of the hierarchy.References: [K1 book] and [K2 book] Positioning of the languages TOTAL, FIN, in the arithmetic hierarchy. Quantified Predicate characterization of the arithmetic Hierarchy. References [K2 book] Exercises Reading Positioning of the languages TOTAL, FIN, in the arithmetic hierarchy. Quantified Predicate characterization of the arithmetic Hierarchy.References: [K2 book] Proof of the quantifier characterization of k-th level of arithmetic hierarchy. References [K2 book], Miscellaneous Excercise 128. <br> The proof idea is based on the <a href="http://www.cse.buffalo.edu/~regan/cse596/AH.pdf"> Notes </a> by Kenneth Regan. Exercises Reading Proof of the quantifier characterization of k-th level of arithmetic hierarchy.References: [K2 book], Miscellaneous Excercise 128.

The proof idea is based on the Notes by Kenneth Regan.Quantifier Characterization of Arithmetic Hierarchy-Continued References The proof idea is based on the <a href="http://www.cse.buffalo.edu/~regan/cse596/AH.pdf"> Notes </a> by Kenneth Regan. Exercises Reading Quantifier Characterization of Arithmetic Hierarchy-ContinuedReferences: The proof idea is based on the Notes by Kenneth Regan. Hardness and Completeness of languages. Halting Problem and Membership Problem are complete for the class of semi-decidable languages. <!Canonical complete problem. Completeness in the higher levels of Arithmetic Hierarchy. MP_k> References [K2 Book] Chapters 35 and 36. Exercises Reading Hardness and Completeness of languages. Halting Problem and Membership Problem are complete for the class of semi-decidable languages.References: [K2 Book] Chapters 35 and 36. Complete problems for the Arithmetic Hierarchy: FIN is complete for the second level. Relativized FIN. <br> Turing and m-degrees. Post's problem. Post's Theorem : There is an semi-decidable but undecidable language which is not complete for the class of semi-decidable languages. Simple and productive sets. Simple sets cannot be co-productive. The self-halting set(K) is co-productive. References [K2] Book Chapters 34 and 35 Exercises Reading Complete problems for the Arithmetic Hierarchy: FIN is complete for the second level. Relativized FIN.

Turing and m-degrees. Post's problem. Post's Theorem : There is an semi-decidable but undecidable language which is not complete for the class of semi-decidable languages. Simple and productive sets. Simple sets cannot be co-productive. The self-halting set(K) is co-productive.References: [K2] Book Chapters 34 and 35 Post's theorem: there is a an r.e. language that is neither recursive nor r.e. complete. Proof of Post's theorem: Simple and productive sets, enumerating Turing machines. References [K2 Book], Chapter 37. Exercises Reading Post's theorem: there is a an r.e. language that is neither recursive nor r.e. complete. Proof of Post's theorem: Simple and productive sets, enumerating Turing machines.References: [K2 Book], Chapter 37. Proof of Post's theorem: Construction of simple sets. complements of Simple sets are not productive. References [K2 Book], Chapter 37. Exercises Reading Proof of Post's theorem: Construction of simple sets. complements of Simple sets are not productive.References: [K2 Book], Chapter 37. Complements of r.e. sets are productive. Statement of Freidberg-Muchnik theorem. Language of Numbers, Peano's Arithmetic. References [K2 Book], CHapter 37, and Chapter 38. Peano's arithmetic is from [K1 book], Lecture 38. Exercises Reading Complements of r.e. sets are productive. Statement of Freidberg-Muchnik theorem. Language of Numbers, Peano's Arithmetic.References: [K2 Book], CHapter 37, and Chapter 38. Peano's arithmetic is from [K1 book], Lecture 38. Godel's First Incompleteness theorem. Theorems and True statements - interpretation of the theorem. A proof of incompleteness using computability. References Lecture 39 in [K1 book] Exercises Reading Godel's First Incompleteness theorem. Theorems and True statements - interpretation of the theorem. A proof of incompleteness using computability.References: Lecture 39 in [K1 book] Proof of Goedel's incompleteness (contd). Concluding remarks on computability. References Lecture 39 in [K1 book] Exercises Reading Proof of Goedel's incompleteness (contd). Concluding remarks on computability.References: Lecture 39 in [K1 book] **Theme 2 : Basic Complexity Theory: Time and Space**- 30 meetings- Meeting 23 : Fri, Sep 06, 10:00 am-10:50 am
- Meeting 24 : Mon, Sep 09, 08:00 am-08:50 am
- Meeting 25 : Tue, Sep 10, 12:00 pm-12:50 pm
- Meeting 26 : Thu, Sep 12, 11:00 am-11:50 am
- Meeting 27 : Fri, Sep 13, 10:00 am-10:50 am
- Meeting 28 : Mon, Sep 16, 08:00 am-08:50 am
- Meeting 29 : Tue, Sep 17, 12:00 pm-12:50 pm
- Meeting 30 : Thu, Sep 19, 11:00 am-11:50 am
- Meeting 31 : Fri, Sep 20, 10:00 am-10:50 am
- Meeting 32 : Mon, Sep 23, 08:00 am-08:50 am
- Meeting 33 : Tue, Sep 24, 12:00 pm-12:50 pm
- Meeting 34 : Thu, Sep 26, 11:00 am-11:50 am
- Meeting 35 : Fri, Sep 27, 10:00 am-10:50 am
- Meeting 36 : Mon, Sep 30, 08:00 am-08:50 am
- Meeting 37 : Thu, Oct 03, 11:00 am-11:50 am
- Meeting 38 : Fri, Oct 04, 10:00 am-10:50 am
- Meeting 39 : Mon, Oct 07, 08:00 am-08:50 am
- Meeting 40 : Tue, Oct 08, 12:00 pm-12:50 pm
- Meeting 41 : Thu, Oct 10, 11:00 am-11:50 am
- Meeting 42 : Fri, Oct 11, 10:00 am-10:50 am
- Meeting 43 : Tue, Oct 15, 12:00 pm-12:50 pm
- Meeting 44 : Thu, Oct 17, 11:00 am-11:50 am
- Meeting 45 : Fri, Oct 18, 10:00 am-10:50 am
- Meeting 46 : Mon, Oct 21, 08:00 am-08:50 am
- Meeting 47 : Tue, Oct 22, 12:00 pm-12:50 pm
- Meeting 48 : Thu, Oct 24, 11:00 am-11:50 am
- Meeting 49 : Fri, Oct 25, 10:00 am-10:50 am
- Meeting 50 : Sat, Oct 26, 09:00 am-10:10 am
- Meeting 51 : Sat, Oct 26, 10:20 am-11:30 am
- Meeting 52 : Mon, Oct 28, 08:00 am-08:50 am

Notion of space and time complexity. Justification of big-oh (O(.)) notation: linear space compression. References [HS], Chapter 5. Exercises Reading Notion of space and time complexity. Justification of big-oh (O(.)) notation: linear space compression.References: [HS], Chapter 5. No lecture--Ganesh Chathurthi References Exercises Reading No lecture--Ganesh ChathurthiReferences: None Why do we use big-Oh notation?-Linear speedup. Robust complexity classes. References [HS], Chapter 5. Exercises Reading Why do we use big-Oh notation?-Linear speedup. Robust complexity classes.References: [HS], Chapter 5. Space hierarchy Theorem. References [MB Notes] chapter 2. Exercises Reading Space hierarchy Theorem.References: [MB Notes] chapter 2. No Lecture: Instructor is out of town. References Exercises Reading No Lecture: Instructor is out of town.References: None Time Hierarchy theorem: Tape reduction. References [MB] notes chapter 2 Exercises Reading Time Hierarchy theorem: Tape reduction.References: [MB] notes chapter 2 First Lower bounds: Crossing sequence arguments. <! A formal view of resources: Blum's Axioms.> References [MB] notes, Chapter 1 Exercises Reading First Lower bounds: Crossing sequence arguments.References: [MB] notes, Chapter 1 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. References [MB Notes] CHapter-1 and Class notes. Exercises Reading 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.References: [MB Notes] CHapter-1 and Class notes. Positioning of computational problems 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. References Class notes. Exercises Reading Positioning of computational problems 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.References: Class notes. Non-deterministic Turing machines. Non-deterministic Time and Space. The classes NP and NL. CLIQUE and SAT are in NP. References Class Notes Exercises Reading Non-deterministic Turing machines. Non-deterministic Time and Space. The classes NP and NL. CLIQUE and SAT are in NP.References: Class Notes CLIQUE is in NP. REACH is in NL. References CLass notes Exercises Reading CLIQUE is in NP. REACH is in NL.References: CLass notes Relation to determinisitic counterparts: L subseteq NL subseteq P subseteq NP subseteq EXP. References Class notes Exercises Reading Relation to determinisitic counterparts: L subseteq NL subseteq P subseteq NP subseteq EXP.References: Class notes No Lecture. Instructor is out of town. References Exercises Reading No Lecture. Instructor is out of town.References: None Notions of reductions and completeness. REACH is NL complete under log-space reductions. References Class notes Exercises Reading Notions of reductions and completeness. REACH is NL complete under log-space reductions.References: Class notes Complementation of NL. Immerman Szelepscenyi Theorem. Proof of Immerman-szelepcsényi theorem. References [MB Notes] Exercises Reading Complementation of NL. Immerman Szelepscenyi Theorem. Proof of Immerman-szelepcsényi theorem.References: [MB Notes] Proof of Immerman-szelepcsényi theorem. Deterministic space bounds for NL: Savitch's theorem. References [MB Notes] Exercises Reading Proof of Immerman-szelepcsényi theorem. Deterministic space bounds for NL: Savitch's theorem.References: [MB Notes] Upper bounds for reachability: Savitch's theorem. References Class Notes Exercises Reading Upper bounds for reachability: Savitch's theorem.References: Class Notes Translation. Time Complexity Classes, P, NP, EXP. Padding Arguments References [MB Notes] Exercises Reading Translation. Time Complexity Classes, P, NP, EXP. Padding ArgumentsReferences: [MB Notes] P = NP implies EXP = NEXP. The Complexity Class NP. A quantifier characterization of NP. References [DK Book], Section 2.1 Exercises Reading P = NP implies EXP = NEXP. The Complexity Class NP. A quantifier characterization of NP.References: [DK Book], Section 2.1 The class CoNP. Relationship between NP, CoNP, P and PSAPCE. Statement of Cook-Levin Theorem: SAT is NP-complete. References Class Notes Exercises Reading The class CoNP. Relationship between NP, CoNP, P and PSAPCE. Statement of Cook-Levin Theorem: SAT is NP-complete.References: Class Notes Proof of Cook-Levin Theorem. References [DK Book], Section 2.2 Exercises Reading Proof of Cook-Levin Theorem.References: [DK Book], Section 2.2 More NP complete problems. References [DK Book], Section 2.3 Exercises Reading More NP complete problems.References: [DK Book], Section 2.3 Ladner's theorem introduction and proof. L References [MB Notes], Chapter 24 Exercises Reading Ladner's theorem introduction and proof. LReferences: [MB Notes], Chapter 24 Ladner's theorem: proof (continued from the last class) References [MB Notes], Chapter 24 Exercises Reading Ladner's theorem: proof (continued from the last class)References: [MB Notes], Chapter 24 Oracle TMs, Turing reduction. Diagonalization and its limitation against Relativization: Baker-Gill-Solovay theorem. References [K2 Book] Chapter 28 Exercises Reading Oracle TMs, Turing reduction. Diagonalization and its limitation against Relativization: Baker-Gill-Solovay theorem.References: [K2 Book] Chapter 28 Proof of Baker-Gill-Solovay. References [K2 Book]Chapter 28 Exercises Reading <a href="http://rjlipton.wordpress.com/2009/05/21/i-hate-oracle-results/"> An interesting article on relativization results by Richard Lipton </a> Proof of Baker-Gill-Solovay.References: [K2 Book]Chapter 28 Reading: An interesting article on relativization results by Richard Lipton Generalizations of NP. 1) Based on oracle access. Relativizations of P and NP. Relativization of NP vs the NP=co-NP question. Definition of Polynomial Hierarchy, References [DK Book], Chapter 3.1 and 3.2 Exercises Reading Generalizations of NP. 1) Based on oracle access. Relativizations of P and NP. Relativization of NP vs the NP=co-NP question. Definition of Polynomial Hierarchy,References: [DK Book], Chapter 3.1 and 3.2 PSPACE completeness of QBF. References [MB notes] Exercises Reading PSPACE completeness of QBF.References: [MB notes] 2) Characterization of PH in terms of Quantifiers. Examples. Circuit Minimization Problem, Formula Isomorphism Problem. References [MB Notes] Exercises Reading 2) Characterization of PH in terms of Quantifiers. Examples. Circuit Minimization Problem, Formula Isomorphism Problem.References: [MB Notes] Alternating Turing machines. Relations to PSPACE and PH. Complete Problems for PH. References [DK Book] and [K2 Book]. Exercises Reading Alternating Turing machines. Relations to PSPACE and PH. Complete Problems for PH.References: [DK Book] and [K2 Book]. **Theme 3 : Counting and Randmization**- 9 meetings- Meeting 53 : Tue, Oct 29, 12:00 pm-12:50 pm
- Meeting 54 : Thu, Oct 31, 11:00 am-11:50 am
- Meeting 55 : Fri, Nov 01, 10:00 am-10:50 am
- Meeting 56 : Mon, Nov 04, 08:00 am-08:50 am
- Meeting 57 : Tue, Nov 05, 12:00 pm-12:50 pm
- Meeting 58 : Thu, Nov 07, 11:00 am-11:50 am
- Meeting 59 : Fri, Nov 08, 10:00 am-10:50 am
- Meeting 60 : Mon, Nov 11, 08:00 am-08:50 am
- Meeting 61 : Tue, Nov 12, 12:00 pm-12:50 pm

Randomization: Probabilistic Complexity Classes: RP, BPP and PP. Success probability amplification. References [MB Notes] Exercises Reading Randomization: Probabilistic Complexity Classes: RP, BPP and PP. Success probability amplification.References: [MB Notes] Probability Amplification, References [MB Notes] Exercises Reading Probability Amplification,References: [MB Notes] Basic Containments. The Polynomial Identity Testing Problem (PIT): Definition of polynomials and arithmetic ciruits. References [MB notes] Exercises Reading Basic Containments. The Polynomial Identity Testing Problem (PIT): Definition of polynomials and arithmetic ciruits.References: [MB notes] Schwartz-Zippel Lemma. Complexity of Counting. References [MB Notes] Exercises Reading Schwartz-Zippel Lemma. Complexity of Counting.References: [MB Notes] Counting: Complexity of counting solutions: Number of Satisfying assignments, cycles in a graph. References [MB Notes], [AB book] Exercises Reading Counting: Complexity of counting solutions: Number of Satisfying assignments, cycles in a graph.References: [MB Notes], [AB book] Counting accepting paths in an NTM. Reductions: parsimonious and many-one. References [MB notes], Class Notes Exercises Reading Counting accepting paths in an NTM. Reductions: parsimonious and many-one.References: [MB notes], Class Notes Counting problems where the corresponding decision version is in P: Counting Perfect matchings in a bipartite graphs. Generalization of counting perfect matchings: permanent of a matrix. Permanent is #P complete under many-one reductions. References [MB Notes] Exercises Reading Counting problems where the corresponding decision version is in P: Counting Perfect matchings in a bipartite graphs. Generalization of counting perfect matchings: permanent of a matrix. Permanent is #P complete under many-one reductions.References: [MB Notes] Permanent is #P complete References [MB Notes]. The gadgets used are from this <a href="http://www.liafa.univ-paris-diderot.fr/~holger/papers/DHMTW12final.pdf"> paper</a> by Dell et. all. See page number 11, for the gadgets. The rest of the arguments are similar to the one in [MB Notes] Exercises Reading Permanent is #P completeReferences: [MB Notes]. The gadgets used are from this paper by Dell et. all. See page number 11, for the gadgets. The rest of the arguments are similar to the one in [MB Notes] How powerful is counting? Toda's Theorem [Without Proof]. BPP and PH. The BP- Operator. Complexity of Graph Isomorphism (GI). If GI is NP-hard, then PH collapses. <!Can Sparse sets be NP complete? Mahaney's theorem.> References [DK Book] Exercises Reading How powerful is counting? Toda's Theorem [Without Proof]. BPP and PH. The BP- Operator. Complexity of Graph Isomorphism (GI). If GI is NP-hard, then PH collapses.References: [DK Book] **Theme 4 : Evaluation Meetings**- 3 meetings- Meeting 62 : Mon, Sep 02, 08:00 am-08:50 am
- Meeting 63 : Mon, Oct 14, 08:00 am-08:50 am
- Meeting 64 : Mon, Nov 18, 02:00 pm-05:00 pm

Quiz-1 References Exercises Reading Quiz-1References: None Quiz-2. Syllabus: Lectures 21-41 References Exercises Reading Quiz-2. Syllabus: Lectures 21-41References: None End Sem. <br> Syllabus: Everything. References Exercises Reading End Sem.

Syllabus: Everything.References: None