CS6014 - Computability and Complexity

Meetings  

• Theme 1 : Computability - 15 meetings

  • Meeting 01 : Mon, Jul 29, 08:00 am-08:50 am

  Administrative Announcements.

  References	[Koz1]
  Exercises
  Reading

  Administrative Announcements.
  

  References:

  [Koz1]

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

  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]

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

  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]

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

  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]

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

  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]

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

  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 ]

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

  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

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

  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

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

  Notion of reductions. Non-recursive languages using reductions.

  References
  Exercises
  Reading

  Notion of reductions. Non-recursive languages using reductions.
  

  References:

  None

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

  Rice's theorem: Part 2.

  References
  Exercises
  Reading

  Rice's theorem: Part 2.
  

  References:

  None

  • Meeting 11 : Fri, Aug 23, 05:30 pm-06:45 pm

  Notion of oracle Turing machines.

  References
  Exercises
  Reading

  Notion of oracle Turing machines.
  

  References:

  None

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

  Relativization. Turing reduction.

  References
  Exercises
  Reading

  Relativization. Turing reduction.
  

  References:

  None

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

  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

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

  Complete Languages in the Arithmetic hierarchy.

  References
  Exercises
  Reading

  Complete Languages in the Arithmetic hierarchy.
  

  References:

  None

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

  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

  Non deterministic Turing Machines. Time complexity: Time bounded TMs.

  References	[Koz2]
  Exercises
  Reading

  Non deterministic Turing Machines. Time complexity: Time bounded TMs.
  

  References:

  [Koz2]

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

  Time hierarchy theorem.

  References
  Exercises
  Reading

  Time hierarchy theorem.
  

  References:

  None

  • Meeting 18 : Fri, Sep 20, 03:30 pm-04:40 pm

  Multi tape vs single tape machines.

  References
  Exercises
  Reading

  Multi tape vs single tape machines.
  

  References:

  None

  • Meeting 19 : Sat, Sep 21, 09:00 am-09:50 am

  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

  • Meeting 20 : Sat, Sep 21, 09:50 am-10:20 am

  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

  • Meeting 21 : Sat, Sep 21, 10:30 am-11:35 am

  Time hierarchy theorem: proof via diagonalization.

  References
  Exercises
  Reading

  Time hierarchy theorem: proof via diagonalization.
  

  References:

  None

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

  Space hierarchy theorem. Concrete Complexity Classes.

  References
  Exercises
  Reading

  Space hierarchy theorem. Concrete Complexity Classes.
  

  References:

  None

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

  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

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

  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

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

  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

  • Meeting 26 : Tue, Oct 01, 12:00 pm-12:50 pm

  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

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

  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

  • Meeting 28 : Fri, Oct 04, 09:00 am-09:50 am

  Between NP and NP-C: Ladner's theorem. Proof.

  References
  Exercises
  Reading

  Between NP and NP-C: Ladner's theorem. Proof.
  

  References:

  None

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

  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

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

  No Lecture.

  References
  Exercises
  Reading

  No Lecture.
  

  References:

  None

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

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

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

  Characterization of PH based on oracle TMs: Full proof.

  References
  Exercises
  Reading

  Characterization of PH based on oracle TMs: Full proof.
  

  References:

  None

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

  PSAPCE: QBF is complete for PSPACE.

  References
  Exercises
  Reading

  PSAPCE: QBF is complete for PSPACE.
  

  References:

  None

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

  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

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

  Immermann-Szelepscenyi: Proof. Padding arguments.

  References
  Exercises
  Reading

  Immermann-Szelepscenyi: Proof. Padding arguments.
  

  References:

  None

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

  Immerman Szelepcenyi

  References
  Exercises
  Reading

  Immerman Szelepcenyi
  

  References:

  None

  • Meeting 37 : Fri, Oct 18, 10:00 am-11:00 am

  Padding Arguments.

  References
  Exercises
  Reading

  Padding Arguments.
  

  References:

  None

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

  Relativization: Baker-Gill-Solovay

  References
  Exercises
  Reading

  Relativization: Baker-Gill-Solovay
  

  References:

  None

• Theme 3 : Randomness in computation and Counting Complexity - 16 meetings

  • Meeting 39 : Tue, Oct 22, 05:00 pm-05:50 pm

  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

  • Meeting 40 : Tue, Oct 22, 05:50 pm-06:40 pm

  Properties of #P.

  References
  Exercises
  Reading

  Properties of #P.
  

  References:

  None

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

  Permanent is #P complete.

  References
  Exercises
  Reading

  Permanent is #P complete.
  

  References:

  None

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

  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

  • Meeting 43 : Fri, Oct 25, 03:30 pm-04:40 pm

  References
  Exercises
  Reading

  
  

  References:

  None

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

  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 RP
  

  References:

  None

  • Meeting 45 : Tue, Oct 29, 12:00 pm-12:50 pm

  Amplification of success probability for BPP. BPP vs PH.

  References
  Exercises
  Reading

  Amplification of success probability for BPP. BPP vs PH.
  

  References:

  None

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

  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

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

  BP operator (contd)

  References
  Exercises
  Reading

  BP operator (contd)
  

  References:

  None

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

  Parity-P. Properties of parity-P.

  References
  Exercises
  Reading

  Parity-P. Properties of parity-P.
  

  References:

  None

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

  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

  • Meeting 50 : Tue, Nov 05, 05:00 pm-06:35 pm

  Valiant-Vazirani Isolation Lemma.

  References
  Exercises
  Reading

  Valiant-Vazirani Isolation Lemma.
  

  References:

  None

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

  Toda's theorem: proof.

  References
  Exercises
  Reading

  Toda's theorem: proof.
  

  References:

  None

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

  Proof systems: Definition and examples. Main results.

  References
  Exercises
  Reading

  Proof systems: Definition and examples. Main results.
  

  References:

  None

  • Meeting 53 : Fri, Nov 08, 03:30 pm-04:45 pm

  Probabilistically Checkable proofs. PCP vs NP. Main results.

  References
  Exercises
  Reading

  Probabilistically Checkable proofs. PCP vs NP. Main results.
  

  References:

  None

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

  GapCSP and PCP. Application to hardness of approximation.

  References
  Exercises
  Reading

  GapCSP and PCP. Application to hardness of approximation.
  

  References:

  None