CS6014 - Advanced Theory of Computation

Meetings  

• Theme 1 : Turing Machines and Computability - 22 meetings

  • Meeting 01 : Mon, Jul 29, 08:00 am-08: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 program

  • Meeting 02 : Tue, Jul 30, 12:00 pm-12:50 pm

  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.
  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.

  • Meeting 03 : Thu, Aug 01, 11:00 am-11:50 am

  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].

  • Meeting 04 : Fri, Aug 02, 10:00 am-10:50 am

  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

  • Meeting 05 : Mon, Aug 05, 08:00 am-08:50 am

  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]

  • Meeting 06 : Tue, Aug 06, 12:00 pm-12:50 pm

  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]

  • Meeting 07 : Thu, Aug 08, 11:00 am-11:50 am

  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]

  • Meeting 08 : Fri, Aug 09, 10:00 am-10:50 am

  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

  • Meeting 09 : Mon, Aug 12, 08:00 am-08:50 am

  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. Proof
  

  References:

  [K1 Book]

  • Meeting 10 : Tue, Aug 13, 12:00 pm-12:50 pm

  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]

  • Meeting 11 : Thu, Aug 15, 11:00 am-11:50 am

  No Lecture: Independence Day.

  References
  Exercises
  Reading

  No Lecture: Independence Day.
  

  References:

  None

  • Meeting 12 : Fri, Aug 16, 10:00 am-10:50 am

  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]

  • Meeting 13 : Mon, Aug 19, 08:00 am-08:50 am

  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]

  • Meeting 14 : Tue, Aug 20, 12:00 pm-12:50 pm

  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.

  • Meeting 15 : Thu, Aug 22, 11:00 am-11:50 am

  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-Continued
  

  References:

  The proof idea is based on the Notes by Kenneth Regan.

  • Meeting 16 : Fri, Aug 23, 10:00 am-10:50 am

  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.

  • Meeting 17 : Mon, Aug 26, 08:00 am-08:50 am

  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

  • Meeting 18 : Tue, Aug 27, 12:00 pm-12:50 pm

  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.

  • Meeting 19 : Thu, Aug 29, 11:00 am-11:50 am

  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.

  • Meeting 20 : Fri, Aug 30, 10:00 am-10:50 am

  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.

  • Meeting 21 : Tue, Sep 03, 12:00 pm-12:50 pm

  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]

  • Meeting 22 : Thu, Sep 05, 11:00 am-11:50 am

  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

  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.

  • Meeting 24 : Mon, Sep 09, 08:00 am-08:50 am

  No lecture--Ganesh Chathurthi

  References
  Exercises
  Reading

  No lecture--Ganesh Chathurthi
  

  References:

  None

  • Meeting 25 : Tue, Sep 10, 12:00 pm-12:50 pm

  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.

  • Meeting 26 : Thu, Sep 12, 11:00 am-11:50 am

  Space hierarchy Theorem.

  References	[MB Notes] chapter 2.
  Exercises
  Reading

  Space hierarchy Theorem.
  

  References:

  [MB Notes] chapter 2.

  • Meeting 27 : Fri, Sep 13, 10:00 am-10:50 am

  No Lecture: Instructor is out of town.

  References
  Exercises
  Reading

  No Lecture: Instructor is out of town.
  

  References:

  None

  • Meeting 28 : Mon, Sep 16, 08:00 am-08:50 am

  Time Hierarchy theorem: Tape reduction.

  References	[MB] notes chapter 2
  Exercises
  Reading

  Time Hierarchy theorem: Tape reduction.
  

  References:

  [MB] notes chapter 2

  • Meeting 29 : Tue, Sep 17, 12:00 pm-12:50 pm

  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

  • Meeting 30 : Thu, Sep 19, 11:00 am-11:50 am

  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.

  • Meeting 31 : Fri, Sep 20, 10:00 am-10:50 am

  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.

  • Meeting 32 : Mon, Sep 23, 08:00 am-08:50 am

  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

  • Meeting 33 : Tue, Sep 24, 12:00 pm-12:50 pm

  CLIQUE is in NP. REACH is in NL.

  References	CLass notes
  Exercises
  Reading

  CLIQUE is in NP. REACH is in NL.
  

  References:

  CLass notes

  • Meeting 34 : Thu, Sep 26, 11:00 am-11:50 am

  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

  • Meeting 35 : Fri, Sep 27, 10:00 am-10:50 am

  No Lecture. Instructor is out of town.

  References
  Exercises
  Reading

  No Lecture. Instructor is out of town.
  

  References:

  None

  • Meeting 36 : Mon, Sep 30, 08:00 am-08:50 am

  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

  • Meeting 37 : Thu, Oct 03, 11:00 am-11:50 am

  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]

  • Meeting 38 : Fri, Oct 04, 10:00 am-10:50 am

  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]

  • Meeting 39 : Mon, Oct 07, 08:00 am-08:50 am

  Upper bounds for reachability: Savitch's theorem.

  References	Class Notes
  Exercises
  Reading

  Upper bounds for reachability: Savitch's theorem.
  

  References:

  Class Notes

  • Meeting 40 : Tue, Oct 08, 12:00 pm-12:50 pm

  Translation. Time Complexity Classes, P, NP, EXP. Padding Arguments

  References	[MB Notes]
  Exercises
  Reading

  Translation. Time Complexity Classes, P, NP, EXP. Padding Arguments
  

  References:

  [MB Notes]

  • Meeting 41 : Thu, Oct 10, 11:00 am-11:50 am

  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

  • Meeting 42 : Fri, Oct 11, 10:00 am-10:50 am

  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

  • Meeting 43 : Tue, Oct 15, 12:00 pm-12:50 pm

  Proof of Cook-Levin Theorem.

  References	[DK Book], Section 2.2
  Exercises
  Reading

  Proof of Cook-Levin Theorem.
  

  References:

  [DK Book], Section 2.2

  • Meeting 44 : Thu, Oct 17, 11:00 am-11:50 am

  More NP complete problems.

  References	[DK Book], Section 2.3
  Exercises
  Reading

  More NP complete problems.
  

  References:

  [DK Book], Section 2.3

  • Meeting 45 : Fri, Oct 18, 10:00 am-10:50 am

  Ladner's theorem introduction and proof. L

  References	[MB Notes], Chapter 24
  Exercises
  Reading

  Ladner's theorem introduction and proof. L
  

  References:

  [MB Notes], Chapter 24

  • Meeting 46 : Mon, Oct 21, 08:00 am-08:50 am

  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

  • Meeting 47 : Tue, Oct 22, 12:00 pm-12:50 pm

  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

  • Meeting 48 : Thu, Oct 24, 11:00 am-11:50 am

  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

  • Meeting 49 : Fri, Oct 25, 10:00 am-10:50 am

  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

  • Meeting 50 : Sat, Oct 26, 09:00 am-10:10 am

  PSPACE completeness of QBF.

  References	[MB notes]
  Exercises
  Reading

  PSPACE completeness of QBF.
  

  References:

  [MB notes]

  • Meeting 51 : Sat, Oct 26, 10:20 am-11:30 am

  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]

  • Meeting 52 : Mon, Oct 28, 08:00 am-08:50 am

  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

  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]

  • Meeting 54 : Thu, Oct 31, 11:00 am-11:50 am

  Probability Amplification,

  References	[MB Notes]
  Exercises
  Reading

  Probability Amplification,
  

  References:

  [MB Notes]

  • Meeting 55 : Fri, Nov 01, 10:00 am-10:50 am

  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]

  • Meeting 56 : Mon, Nov 04, 08:00 am-08:50 am

  Schwartz-Zippel Lemma. Complexity of Counting.

  References	[MB Notes]
  Exercises
  Reading

  Schwartz-Zippel Lemma. Complexity of Counting.
  

  References:

  [MB Notes]

  • Meeting 57 : Tue, Nov 05, 12:00 pm-12:50 pm

  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]

  • Meeting 58 : Thu, Nov 07, 11:00 am-11:50 am

  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

  • Meeting 59 : Fri, Nov 08, 10:00 am-10:50 am

  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]

  • Meeting 60 : Mon, Nov 11, 08:00 am-08:50 am

  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 complete
  

  References:

  [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]

  • Meeting 61 : Tue, Nov 12, 12:00 pm-12:50 pm

  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

  Quiz-1

  References
  Exercises
  Reading

  Quiz-1
  

  References:

  None

  • Meeting 63 : Mon, Oct 14, 08:00 am-08:50 am

  Quiz-2. Syllabus: Lectures 21-41

  References
  Exercises
  Reading

  Quiz-2. Syllabus: Lectures 21-41
  

  References:

  None

  • Meeting 64 : Mon, Nov 18, 02:00 pm-05:00 pm

  End Sem. <br> Syllabus: Everything.

  References
  Exercises
  Reading

  End Sem.
  Syllabus: Everything.
  

  References:

  None