CS6840 - Modern Complexity Theory

Meetings  

• Theme 1 : Counting and Probabilistic Computation - 16 meetings

  • Meeting 01 : Tue, Jan 16, 11:00 am-11:50 am

  Administrative announcements. Brief review of complexity classes.

  References
  Exercises
  Reading

  Administrative announcements. Brief review of complexity classes.
  

  References:

  None

  • Meeting 02 : Wed, Jan 17, 10:00 am-10:50 am

  Decision vs Computational problems. Counting problems: Counting Spanning trees, counting perfect matchings, coutning satisfying assignments. Kirchoff's theorem.

  References	For Kirchoff's theorem Please see Van Lint's book on Combinatorics.
  Exercises
  Reading

  Decision vs Computational problems. Counting problems: Counting Spanning trees, counting perfect matchings, coutning satisfying assignments. Kirchoff's theorem.
  

  References:

  For Kirchoff's theorem Please see Van Lint's book on Combinatorics.

  • Meeting 03 : Thu, Jan 18, 08:00 am-08:50 am

  Proof of Kirchoff's theorem. An algorithm for #SAT. Definition of #P.

  References	[MBNotes]
  Exercises
  Reading

  Proof of Kirchoff's theorem. An algorithm for #SAT. Definition of #P.
  

  References:

  [MBNotes]

  • Meeting 04 : Wed, Jan 24, 10:00 am-10:50 am

  FP is in #P. Characterizations of #P. Parsimonious reductions. #SAT is complete for #P under parsimonious reductions. Polynomial time reductions for counting problems.

  References	[MBNotes]
  Exercises
  Reading

  FP is in #P. Characterizations of #P. Parsimonious reductions. #SAT is complete for #P under parsimonious reductions. Polynomial time reductions for counting problems.
  

  References:

  [MBNotes]

  • Meeting 05 : Wed, Jan 24, 10:50 am-11:45 am

  Permanent. Relation to perfect matchings in bipartite graphs an dcycle covers.

  References	[MBNotes]
  Exercises
  Reading

  Permanent. Relation to perfect matchings in bipartite graphs an dcycle covers.
  

  References:

  [MBNotes]

  • Meeting 06 : Thu, Jan 25, 08:00 am-08:50 am

  Valiant's theorem (proof).

  References	[MBNotes]. The gadgets used in the class is from <a href="https://arxiv.org/abs/1206.1775"> Link </a> Page 11.
  Exercises
  Reading

  Valiant's theorem (proof).
  

  References:

  [MBNotes]. The gadgets used in the class is from Link Page 11.

  • Meeting 07 : Thu, Jan 25, 08:50 am-09:40 am

  Valiant's theorem (Proof). From counting to decision. Bit language of a function.

  References	[MBNotes]
  Exercises
  Reading

  Valiant's theorem (Proof). From counting to decision. Bit language of a function.
  

  References:

  [MBNotes]

  • Meeting 08 : Tue, Jan 30, 11:00 am-11:50 am

  Comparing values of two #P functions. Definition of PP. Probabilistic computation. Probabilistic complexity classes: RP , BPP and PP.

  References
  Exercises
  Reading

  Comparing values of two #P functions. Definition of PP. Probabilistic computation. Probabilistic complexity classes: RP , BPP and PP.
  

  References:

  None

  • Meeting 09 : Wed, Jan 31, 10:00 am-10:50 am

  Probabilistic complexity classes. The two definitions of PP are equivalent. Polynomial identity testing. Amplification of success probability (one sided error).

  References	<a href="https://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture11.pdf"> Notes </a> from an earlier offering of the course.
  Exercises
  Reading

  Probabilistic complexity classes. The two definitions of PP are equivalent. Polynomial identity testing. Amplification of success probability (one sided error).
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 10 : Wed, Jan 31, 11:00 am-11:50 am

  Amplification of success probability (two sided error). RP is contained in NP. BPP is contained in PSPACE.

  References	<a href="https://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture11.pdf"> Notes </a> from an earlier offering of the course.
  Exercises
  Reading

  Amplification of success probability (two sided error). RP is contained in NP. BPP is contained in PSPACE.
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 11 : Thu, Feb 01, 08:00 am-08:50 am

  Relationship to other complexity classes. PP vs #P. BPP is in PH.

  References
  Exercises
  Reading

  Relationship to other complexity classes. PP vs #P. BPP is in PH.
  

  References:

  None

  • Meeting 12 : Tue, Feb 06, 11:00 am-11:50 am

  BPP is in PH (contd).

  References
  Exercises
  Reading

  BPP is in PH (contd).
  

  References:

  None

  • Meeting 13 : Wed, Feb 07, 10:00 am-10:50 am

  The class Parity P. Parity operator. Closure properties of parity operator.

  References
  Exercises
  Reading

  The class Parity P. Parity operator. Closure properties of parity operator.
  

  References:

  None

  • Meeting 14 : Wed, Feb 07, 11:00 am-11:50 am

  Parity operator is closed under majority and Turing reductions. Valiant Vazirani Theorem. Pairwise independent hash families.

  References
  Exercises
  Reading

  Parity operator is closed under majority and Turing reductions. Valiant Vazirani Theorem. Pairwise independent hash families.
  

  References:

  None

  • Meeting 15 : Thu, Feb 08, 08:00 am-08:50 am

  Proof of Valiant- Vazirani theorem. The BP operator. Swapping Exists with BP operator.

  References	<a href="https://theoryofcomputing.org/articles/v005a007/v005a007.pdf"> A simple proof of Toda's theorem</a>, Note by Lance Fortnow
  Exercises
  Reading

  Proof of Valiant- Vazirani theorem. The BP operator. Swapping Exists with BP operator.
  

  References:

  A simple proof of Toda's theorem, Note by Lance Fortnow

  • Meeting 16 : Tue, Feb 13, 11:00 am-11:50 am

  Swapping exists with BP operator. BP-parity P is in P^#P.

  References
  Exercises
  Reading	<a href="https://rjlipton.wordpress.com/2009/07/01/the-isolation-lemma-and-beyond/"> Isolation lemma and beyond</a> A blog post by Dick Lipton. The Satanic Notations: Counting Classes Beyond #P and Other Definitional Adventures by Hemspaandra and Vollmer, ACM SIGACT News 1995.

  Swapping exists with BP operator. BP-parity P is in P^#P.
  

  References:	None
  Reading:	Isolation lemma and beyond A blog post by Dick Lipton. The Satanic Notations: Counting Classes Beyond #P and Other Definitional Adventures by Hemspaandra and Vollmer, ACM SIGACT News 1995.

• Theme 2 : Boolean Circuits - 24 meetings

  • Meeting 17 : Thu, Feb 15, 08:00 am-08:50 am

  The class P/poly. BPP is in P/poly. Circuit definition of P/poly. Karp-Lipton Theorem.

  References	Blaeser's notes.
  Exercises
  Reading

  The class P/poly. BPP is in P/poly. Circuit definition of P/poly. Karp-Lipton Theorem.
  

  References:

  Blaeser's notes.

  • Meeting 18 : Tue, Feb 20, 11:00 am-11:50 am

  Circuits as a model for computation. Post's characterization of a complete basis. Resources: Size, depth and width.

  References	<a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture34.pdf"> Notes </a> from an earlier offering of the course.
  Exercises
  Reading

  Circuits as a model for computation. Post's characterization of a complete basis. Resources: Size, depth and width.
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 19 : Wed, Feb 21, 10:00 am-10:50 am

  Size of a circuit. Shannon's lower bound.

  References	<a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture35.pdf"> Notes </a> from an earlier offering of the course.
  Exercises
  Reading

  Size of a circuit. Shannon's lower bound.
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 20 : Wed, Feb 21, 11:00 am-11:50 am

  Lupanov's upper bound.

  References	<a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture35.pdf"> Notes </a> from an earlier offering of the course.
  Exercises
  Reading

  Lupanov's upper bound.
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 21 : Thu, Feb 22, 08:00 am-08:50 am

  No lecture.

  References
  Exercises
  Reading

  No lecture.
  

  References:

  None

  • Meeting 22 : Tue, Feb 27, 11:00 am-11:50 am

  Circuit complexity classes. NC and AC hierarchies. Upper bounds: parity, add, compare.

  References	See [Vollmer] for a detailed exposition
  Exercises
  Reading

  Circuit complexity classes. NC and AC hierarchies. Upper bounds: parity, add, compare.
  

  References:

  See [Vollmer] for a detailed exposition

  • Meeting 23 : Wed, Feb 28, 10:00 am-10:50 am

  Special classes of circuits: Formulas. Formulas == NC1 (Brent)

  References	See [Vollmer] for a detailed exposition
  Exercises
  Reading

  Special classes of circuits: Formulas. Formulas == NC1 (Brent)
  

  References:

  See [Vollmer] for a detailed exposition

  • Meeting 24 : Wed, Feb 28, 11:00 am-11:20 am

  Formulas == NC1 (contd) Branching programs. Branching programs = NL

  References	See [Vollmer] for a detailed exposition
  Exercises
  Reading

  Formulas == NC1 (contd) Branching programs. Branching programs = NL
  

  References:

  See [Vollmer] for a detailed exposition

  • Meeting 25 : Thu, Mar 01, 08:00 am-08:50 am

  Skew circuits. Skew circuits vs BPs.

  References	See [Vollmer] or Lecture <a href ="http://www.cs.au.dk/~arnsfelt/CT10/scribenotes/lecture16.pdf"> notes </a> by Kristoffer Hansen
  Exercises
  Reading

  Skew circuits. Skew circuits vs BPs.
  

  References:

  See [Vollmer] or Lecture notes by Kristoffer Hansen

  • Meeting 26 : Tue, Mar 06, 11:00 am-11:50 am

  Bounded width Branching Programs. Barrington's theorem. Vertex labels vs edge labels. Permutation BPs.

  References
  Exercises
  Reading

  Bounded width Branching Programs. Barrington's theorem. Vertex labels vs edge labels. Permutation BPs.
  

  References:

  None

  • Meeting 27 : Wed, Mar 07, 10:00 am-10:50 am

  Proof of Barrington's thm.

  References
  Exercises
  Reading

  Proof of Barrington's thm.
  

  References:

  None

  • Meeting 28 : Wed, Mar 07, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 29 : Thu, Mar 08, 08:00 am-08:50 am

  Back to the circuit lower bound problem. Need for lower bound against explicit functions. 2n-4 lower bound for Th. 3(n-1) lower bound for parity.

  References
  Exercises
  Reading

  Back to the circuit lower bound problem. Need for lower bound against explicit functions. 2n-4 lower bound for Th. 3(n-1) lower bound for parity.
  

  References:

  None

  • Meeting 30 : Fri, Mar 09, 02:00 pm-02:50 pm

  Formula size lower bounds: Universal functions. Method of restrictions. Lower bound for parity.

  References
  Exercises
  Reading

  Formula size lower bounds: Universal functions. Method of restrictions. Lower bound for parity.
  

  References:

  None

  • Meeting 31 : Tue, Mar 13, 11:00 am-11:50 am

  Subbotovoskaya's random restriction. Andreev's lower bound.

  References
  Exercises
  Reading

  Subbotovoskaya's random restriction. Andreev's lower bound.
  

  References:

  None

  • Meeting 32 : Wed, Mar 14, 10:00 am-10:50 am

  Nechiporuk's lower bound. Bounded depth circuits.

  References
  Exercises
  Reading

  Nechiporuk's lower bound. Bounded depth circuits.
  

  References:

  None

  • Meeting 33 : Thu, Mar 15, 08:00 am-08:50 am

  Parity is not in AC0.

  References
  Exercises
  Reading

  Parity is not in AC0.
  

  References:

  None

  • Meeting 34 : Thu, Mar 15, 09:00 am-09:50 am

  Hastad's switching lemma. Razborov's proof.

  References
  Exercises
  Reading

  Hastad's switching lemma. Razborov's proof.
  

  References:

  None

  • Meeting 35 : Tue, Mar 20, 11:00 am-11:50 am

  Polynomial method for circuit lower bounds. Representing Boolean functions as polynomials. Approximating Boolean functions by polynomials of low degree.

  References	Blaeser's notes.
  Exercises
  Reading

  Polynomial method for circuit lower bounds. Representing Boolean functions as polynomials. Approximating Boolean functions by polynomials of low degree.
  

  References:

  Blaeser's notes.

  • Meeting 36 : Wed, Mar 21, 10:00 am-10:50 am

  Low degree approximation of constant depth circuits.

  References
  Exercises
  Reading

  Low degree approximation of constant depth circuits.
  

  References:

  None

  • Meeting 37 : Wed, Mar 21, 11:00 am-11:50 am

  Parity has no low degree approximation.

  References
  Exercises
  Reading

  Parity has no low degree approximation.
  

  References:

  None

  • Meeting 38 : Thu, Mar 22, 08:00 am-08:50 am

  Monotone circuits. Clique cannot be computed by polynomial size monotone circuits.

  References
  Exercises
  Reading

  Monotone circuits. Clique cannot be computed by polynomial size monotone circuits.
  

  References:

  None

  • Meeting 39 : Thu, Mar 22, 09:00 am-09:50 am

  Razborov's proof of monotone circuit lower bound for clique.

  References
  Exercises
  Reading

  Razborov's proof of monotone circuit lower bound for clique.
  

  References:

  None

  • Meeting 40 : Tue, Mar 27, 11:00 am-11:50 am

  Razborov's proof (contd)

  References
  Exercises
  Reading

  Razborov's proof (contd)
  

  References:

  None

• Theme 3 : Proof Systems - 8 meetings

  • Meeting 41 : Thu, Apr 05, 08:30 am-09:20 am

  Interactive proof systems: Introduction. Deterministic vs probabilistic verifier.

  References
  Exercises
  Reading

  Interactive proof systems: Introduction. Deterministic vs probabilistic verifier.
  

  References:

  None

  • Meeting 42 : Tue, Apr 10, 11:00 am-11:50 am

  Definition of IP. A proof system for Graph non isomorphism. Public coin proof systems. Definition of AM and MA. AM protocol for GNI?

  References
  Exercises
  Reading

  Definition of IP. A proof system for Graph non isomorphism. Public coin proof systems. Definition of AM and MA. AM protocol for GNI?
  

  References:

  None

  • Meeting 43 : Wed, Apr 11, 10:00 am-10:50 am

  AM protocol for GNI. Goldwasser Sipser set lower bound protocol. Consequence: GI cannot be NP complete unless PH collapses!!

  References
  Exercises
  Reading

  AM protocol for GNI. Goldwasser Sipser set lower bound protocol. Consequence: GI cannot be NP complete unless PH collapses!!
  

  References:

  None

  • Meeting 44 : Wed, Apr 11, 11:00 am-12:00 pm

  Shamir's theorem: IP = PSPACE. Arithmetization of QBF. IP for QBF.

  References
  Exercises
  Reading

  Shamir's theorem: IP = PSPACE. Arithmetization of QBF. IP for QBF.
  

  References:

  None

  • Meeting 45 : Thu, Apr 12, 08:00 am-08:50 am

  IP for QBF (contd).

  References
  Exercises
  Reading

  IP for QBF (contd).
  

  References:

  None

  • Meeting 46 : Thu, Apr 12, 09:00 am-10:00 am

  Introduction to PCP.

  References
  Exercises
  Reading

  Introduction to PCP.
  

  References:

  None

  • Meeting 47 : Tue, Apr 17, 11:00 am-11:50 am

  PCP and hardness of approximation.

  References
  Exercises
  Reading

  PCP and hardness of approximation.
  

  References:

  None

  • Meeting 48 : Tue, Apr 24, 11:00 am-11:50 am

  PCP for LIN.

  References
  Exercises
  Reading

  PCP for LIN.
  

  References:

  None

• Theme 4 : Derandomization - 6 meetings

  • Meeting 49 : Wed, Mar 28, 10:00 am-10:50 am

  Recap of randomized computation. The de-randomization problem.

  References
  Exercises
  Reading

  Recap of randomized computation. The de-randomization problem.
  

  References:

  None

  • Meeting 50 : Wed, Mar 28, 11:00 am-12:00 pm

  Definition of pseudorandom generators (PRG). Efficient PRG implies BPP = P. Overview of NW generator.

  References	[Blaeser Notes] or the orignial article " Hardness vs Randomness" by Nisan and Wigderson.
  Exercises
  Reading

  Definition of pseudorandom generators (PRG). Efficient PRG implies BPP = P. Overview of NW generator.
  

  References:

  [Blaeser Notes] or the orignial article " Hardness vs Randomness" by Nisan and Wigderson.

  • Meeting 51 : Tue, Apr 03, 11:00 am-11:50 am

  From hardness to PRG: NW construction. Combinatorial designs. Definition of the NW generator. Hybrid argument.

  References	[Blaeser Notes] or the orignial article " Hardness vs Randomness" by Nisan and Wigderson.
  Exercises
  Reading

  From hardness to PRG: NW construction. Combinatorial designs. Definition of the NW generator. Hybrid argument.
  

  References:

  [Blaeser Notes] or the orignial article " Hardness vs Randomness" by Nisan and Wigderson.

  • Meeting 52 : Wed, Apr 04, 10:00 am-10:50 am

  Proof of correctness for the NW generator. Existence of Combinatorial designs.

  References
  Exercises
  Reading

  Proof of correctness for the NW generator. Existence of Combinatorial designs.
  

  References:

  None

  • Meeting 53 : Wed, Apr 04, 11:00 am-12:00 pm

  Randomness to Hardness. ACIT in P implies circuit lower bounds.

  References	[Blaeser Notes] or Original <a href="https://www.cs.sfu.ca/~kabanets/Research/poly.html"> article </a> by kabanets and Impagliazzo.
  Exercises
  Reading

  Randomness to Hardness. ACIT in P implies circuit lower bounds.
  

  References:

  [Blaeser Notes] or Original article by kabanets and Impagliazzo.

  • Meeting 54 : Thu, Apr 05, 08:00 am-08:30 am

  (short lecture) ACIT in P implies circuit lower bounds (contd)

  References
  Exercises
  Reading

  (short lecture) ACIT in P implies circuit lower bounds (contd)
  

  References:

  None

• Theme 5 : Evaluation - 2 meetings

  • Meeting 55 : Wed, Apr 25, 10:00 am-12:00 pm

  Presentations: 1) Sagar 2)Dheeraj 3)Utsab Duration: 40 min each

  References
  Exercises
  Reading

  Presentations: 1) Sagar 2)Dheeraj 3)Utsab Duration: 40 min each
  

  References:

  None

  • Meeting 56 : Thu, Apr 26, 08:00 am-08:50 am

  Presentations 1) Sameer 2) Tejas 3) Ankit Duration: 40 min each

  References
  Exercises
  Reading

  Presentations 1) Sameer 2) Tejas 3) Ankit Duration: 40 min each
  

  References:

  None