CS6840 - Advanced Complexity Theory

Meetings  

• Theme 1 : Counting and Randomness - 7 meetings

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

  Administrative Announcements. Overview of the course.

  References	None
  Exercises
  Reading

  Administrative Announcements. Overview of the course.
  

  References:

  None

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

  Toda's theorem, introduction. Isolation Lemma.

  References	[MB Notes1], Chapters 16 and 17.
  Exercises
  Reading

  Toda's theorem, introduction. Isolation Lemma.
  

  References:

  [MB Notes1], Chapters 16 and 17.

  • Meeting 03 : Mon, Jan 20, 08:00 am-08:50 am -

  An application of isolation: Valiant-Vazirani Theorem, randomly isolating a unique satisfying assignment. <! A randomized parallel algorithm for perfect matching (Mulmuley-Vazirani-Vazirani)>.

  References	[MBNotes1]
  Exercises
  Reading

  An application of isolation: Valiant-Vazirani Theorem, randomly isolating a unique satisfying assignment. .
  

  References:

  [MBNotes1]

  • Meeting 04 : Tue, Jan 21, 12:00 pm-12:50 pm -

  Proof of Toda's theorem: Properties of parityP: parityP is closed under complements and Turing reductions.

  References	[MBNotes1]
  Exercises
  Reading

  Proof of Toda's theorem: Properties of parityP: parityP is closed under complements and Turing reductions.
  

  References:

  [MBNotes1]

  • Meeting 05 : Thu, Jan 23, 11:00 am-11:50 am -

  The BP operator. NP is contained in NP-parityP. Amplification of success probability.

  References	[MBNotes]
  Exercises
  Reading

  The BP operator. NP is contained in NP-parityP. Amplification of success probability.
  

  References:

  [MBNotes]

  • Meeting 06 : Fri, Jan 24, 10:00 am-10:50 am -

  Elimination of quantifiers from exists BP-parityP.

  References	[MBNotes]
  Exercises
  Reading

  Elimination of quantifiers from exists BP-parityP.
  

  References:

  [MBNotes]

  • Meeting 07 : Mon, Jan 27, 08:00 am-08:50 am -

  BP-parityP is contained in P^#P.

  References	[MBNotes]
  Exercises
  Reading

  BP-parityP is contained in P^#P.
  

  References:

  [MBNotes]

• Theme 2 : Proof Systems, PCP - 21 meetings

  • Meeting 08 : Tue, Jan 28, 12:00 pm-12:50 pm -

  Introductions to proof systems. Interactive proof systems. Example: Graph isomorphism. The complexity class IP.

  References	[MBNotes1]
  Exercises
  Reading	<a href="http://people.cs.uchicago.edu/~laci/papers/email90.pdf"> E-mail and the unexpected power of interaction </a> A nice expository article on interactive proofs by L. Babai. A must read.

  Introductions to proof systems. Interactive proof systems. Example: Graph isomorphism. The complexity class IP.
  

  References:	[MBNotes1]
  Reading:	E-mail and the unexpected power of interaction A nice expository article on interactive proofs by L. Babai. A must read.

  • Meeting 09 : Thu, Jan 30, 11:00 am-11:50 am -

  IP is contained in PSPACE.

  References	[MBNotes1]
  Exercises
  Reading

  IP is contained in PSPACE.
  

  References:

  [MBNotes1]

  • Meeting 10 : Fri, Jan 31, 10:00 am-10:50 am -

  IP is contained in PSPACE (contd). Shamir's theorem - IP=PSPACE Arithmetization of QBF.

  References	For IP in PSPACE see CHapter 17 of [K Book]. [MBNotes1]
  Exercises
  Reading

  IP is contained in PSPACE (contd). Shamir's theorem - IP=PSPACE Arithmetization of QBF.
  

  References:

  For IP in PSPACE see CHapter 17 of [K Book]. [MBNotes1]

  • Meeting 11 : Mon, Feb 03, 08:00 am-08:50 am -

  IP=PSPACE (contd)

  References	[MBNotes1]
  Exercises
  Reading

  IP=PSPACE (contd)
  

  References:

  [MBNotes1]

  • Meeting 12 : Tue, Feb 04, 12:00 pm-12:50 pm -

  IP=PSPACE (contd).

  References	[MBNotes2]
  Exercises
  Reading	<a href="http://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf">A historical perspective </a> on probabilistically checkable proofs

  IP=PSPACE (contd).
  

  References:	[MBNotes2]
  Reading:	A historical perspective on probabilistically checkable proofs

  • Meeting 13 : Thu, Feb 06, 11:00 am-11:50 am -

  Graph isomorphism revisited. The class AM. GI cannot be NP complete unless the PH collapses.

  References	<a href="http://www.cs.princeton.edu/courses/archive/spring06/cos522/ip.pdf"> Notes</a> by Boaz Barak. Also see <a href="http://www.iarcs.org.in/activities/elnotes/pdf/ip.pdf"> Notes </a> on interactive proofs by Jaikumar Radhakrishnan.
  Exercises
  Reading

  Graph isomorphism revisited. The class AM. GI cannot be NP complete unless the PH collapses.
  

  References:

  Notes by Boaz Barak. Also see Notes on interactive proofs by Jaikumar Radhakrishnan.

  • Meeting 14 : Fri, Feb 07, 10:00 am-10:50 am -

  Graph isomorphism (contd): Goldwasser-Sipser set lower bound protocol. Probabilistically Checkable Proofs [PCP]: Introduction.

  References	[MBNotes2]. Also see <a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> notes </a> by Andrej Bogdanov.
  Exercises
  Reading	<a href="http://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf"> A History of the PCP theorem </a> by Ryan O'Donnel, a nice read on the history of interactive proofs and PCP.

  Graph isomorphism (contd): Goldwasser-Sipser set lower bound protocol. Probabilistically Checkable Proofs [PCP]: Introduction.
  

  References:	[MBNotes2]. Also see notes by Andrej Bogdanov.
  Reading:	A History of the PCP theorem by Ryan O'Donnel, a nice read on the history of interactive proofs and PCP.

  • Meeting 15 : Mon, Feb 10, 08:00 am-08:50 am -

  PCP theorems. Statements and applications.

  References	[MBNotes2] and a <a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> lecture notes</a> by A. Bogdanov.
  Exercises
  Reading

  PCP theorems. Statements and applications.
  

  References:

  [MBNotes2] and a lecture notes by A. Bogdanov.

  • Meeting 16 : Tue, Feb 11, 12:00 pm-12:50 pm -

  Promise problems with a gap: Gap-SAT, Gap-CSP. PCP theorem is equivalent to "Gap-SAT is NP complete"

  References	[MBNotes2], Bogdanov's Lecture <a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Notes</a>
  Exercises
  Reading

  Promise problems with a gap: Gap-SAT, Gap-CSP. PCP theorem is equivalent to "Gap-SAT is NP complete"
  

  References:

  [MBNotes2], Bogdanov's Lecture Notes

  • Meeting 17 : Thu, Feb 13, 11:00 am-11:50 am -

  Gap-SAT vs PCP. Hardness of GAP-SAT implies hardness of approximation.

  References	[MBNotes2] <a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading

  Gap-SAT vs PCP. Hardness of GAP-SAT implies hardness of approximation.
  

  References:

  [MBNotes2] Notes by Bogdanov.

  • Meeting 18 : Fri, Feb 14, 10:00 am-10:50 am -

  A PCP for LIN (feasible system of linear equations). A Linearity test.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Lecture notes</a> by A. Bogdanov.
  Exercises
  Reading

  A PCP for LIN (feasible system of linear equations). A Linearity test.
  

  References:

  Lecture notes by A. Bogdanov.

  • Meeting 19 : Mon, Feb 17, 08:00 am-08:50 am -

  BLR Linearity Test. PCP for Lin continued.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading

  BLR Linearity Test. PCP for Lin continued.
  

  References:

  Notes by Bogdanov.

  • Meeting 20 : Tue, Feb 18, 12:00 pm-12:50 pm -

  PCP for LIN continued.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading

  PCP for LIN continued.
  

  References:

  Notes by Bogdanov.

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

  A weak PCP theorem. Weak PCP (contd).

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading

  A weak PCP theorem. Weak PCP (contd).
  

  References:

  Notes by Bogdanov.

  • Meeting 22 : Fri, Feb 21, 10:00 am-10:50 am -

  Introduction to Dinur's Proof of PCP Theorem.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading

  Introduction to Dinur's Proof of PCP Theorem.
  

  References:

  Notes by Bogdanov.

  • Meeting 23 : Mon, Feb 24, 08:00 am-08:50 am -

  Expander graphs: a quick overview. Notion of expander graphs. Connections to eigen values.

  References	[MBnotes2] Chapters 7 and 8. Bogdanov lecture notes~7.
  Exercises
  Reading	An excellent and comprehensive <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf"> survey</a> of expander graphs. A set of <a href="http://www.math.ias.edu/~boaz/ExpanderCourse/allnotes.pdf"> notes </a> by Linial and Wigderson is also a good read on expanders and their applications.

  Expander graphs: a quick overview. Notion of expander graphs. Connections to eigen values.
  

  References:	[MBnotes2] Chapters 7 and 8. Bogdanov lecture notes~7.
  Reading:	An excellent and comprehensive survey of expander graphs. A set of notes by Linial and Wigderson is also a good read on expanders and their applications.

  • Meeting 24 : Tue, Feb 25, 12:00 pm-12:50 pm -

  Algebraic Expansion. Construction of expander graphs. Replacement product.

  References	[MBnotes2] Chapters 7 and 8. Chapter 21 from [AB Book]
  Exercises
  Reading	An excellent and comprehensive <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf"> survey</a> of expander graphs. A set of <a href="http://www.math.ias.edu/~boaz/ExpanderCourse/allnotes.pdf"> notes </a> by Linial and Wigderson is also a good read on expanders and their applications.

  Algebraic Expansion. Construction of expander graphs. Replacement product.
  

  References:	[MBnotes2] Chapters 7 and 8. Chapter 21 from [AB Book]
  Reading:	An excellent and comprehensive survey of expander graphs. A set of notes by Linial and Wigderson is also a good read on expanders and their applications.

  • Meeting 25 : Thu, Feb 27, 11:00 am-11:50 am -

  Construction of expander graphs (contd). Dinur's proof: Step 1 : Query reduction.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L13.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading

  Construction of expander graphs (contd). Dinur's proof: Step 1 : Query reduction.
  

  References:

  Notes by Bogdanov.

  • Meeting 26 : Fri, Feb 28, 10:00 am-10:50 am -

  Dinur's proof: Step 2: Degree reduction.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L13.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading	A nice expository <a href="http://people.csail.mit.edu/madhu/papers/2006/jaikumar.pdf" article</a> on Dinur's proof by Jaikumar Radhakrishnan and Madhu Sudan.

  Dinur's proof: Step 2: Degree reduction.
  

  References:	Notes by Bogdanov.
  Reading:	A nice expository on Dinur's proof by Jaikumar Radhakrishnan and Madhu Sudan.

  • Meeting 27 : Mon, Mar 03, 08:00 am-08:50 am -

  Degree Reduction (contd). Dinur's proof: Step 3: Expanderization.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L13.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading	A nice expository <a href="http://people.csail.mit.edu/madhu/papers/2006/jaikumar.pdf" article</a> on Dinur's proof by Jaikumar Radhakrishnan and Madhu Sudan.

  Degree Reduction (contd). Dinur's proof: Step 3: Expanderization.
  

  References:	Notes by Bogdanov.
  Reading:	A nice expository on Dinur's proof by Jaikumar Radhakrishnan and Madhu Sudan.

  • Meeting 28 : Tue, Mar 04, 12:00 pm-12:50 pm -

  Gap Amplification. Alphabet reduction. Putting them all together.

  References	<a href="http://www.cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L12.pdf"> Notes</a> by Bogdanov.
  Exercises
  Reading	A nice expository <a href="http://people.csail.mit.edu/madhu/papers/2006/jaikumar.pdf" article</a> on Dinur's proof by Jaikumar Radhakrishnan and Madhu Sudan.

  Gap Amplification. Alphabet reduction. Putting them all together.
  

  References:	Notes by Bogdanov.
  Reading:	A nice expository on Dinur's proof by Jaikumar Radhakrishnan and Madhu Sudan.

• Theme 3 : Boolean Circuits - 25 meetings

  • Meeting 29 : Thu, Mar 06, 11:00 am-11:50 am -

  Introduction to Boolean circuits. Post's characterization of Complete Bases for Boolean circuits.

  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

  Introduction to Boolean circuits. Post's characterization of Complete Bases for Boolean circuits.
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 30 : Fri, Mar 07, 10:00 am-10:50 am -

  Resource measures on circuits: Size Depth, fan-in and fan-out. Formulas. Most functions are hard, Shanon'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

  Resource measures on circuits: Size Depth, fan-in and fan-out. Formulas. Most functions are hard, Shanon's lower bound.
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 31 : Mon, Mar 10, 08:00 am-08:50 am -

  Shannon's lower bound (contd). Lupanov's upper bound.

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

  Shannon's lower bound (contd). Lupanov's upper bound.
  

  References:

  Notes from an earlier offering of the course.

  • Meeting 32 : Tue, Mar 11, 12:00 pm-12:50 pm -

  Uniformity in circuits. Simulation of Turing machines by circuits.

  References	<a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture37.pdf"> Notes </a> from an earlier offering of the course.
  Exercises
  Reading	Heribert Vollmer: Introduction to Circuit Complexity (A Uniform Approach), Springer-Verlag 1999

  Uniformity in circuits. Simulation of Turing machines by circuits.
  

  References:	Notes from an earlier offering of the course.
  Reading:	Heribert Vollmer: Introduction to Circuit Complexity (A Uniform Approach), Springer-Verlag 1999

  • Meeting 33 : Thu, Mar 13, 11:00 am-11:50 am -

  Circuits as non-uniform models of computation: the class P/poly. NP vs P/poly: Karp Lipton theorem.

  References	[MB Notes]
  Exercises
  Reading

  Circuits as non-uniform models of computation: the class P/poly. NP vs P/poly: Karp Lipton theorem.
  

  References:

  [MB Notes]

  • Meeting 34 : Fri, Mar 14, 10:00 am-10:50 am -

  The classes NC, AC, and SC. Parity in NC1, Reachin NC2. NC1 is contained in Logspace.

  References	[MBNotes], <a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture39.pdf"> Notes </a> from the earlier offering of this course.
  Exercises
  Reading

  The classes NC, AC, and SC. Parity in NC1, Reachin NC2. NC1 is contained in Logspace.
  

  References:

  [MBNotes], Notes from the earlier offering of this course.

  • Meeting 35 : Mon, Mar 17, 08:00 am-08:50 am -

  No Lecture (Holi)

  References
  Exercises
  Reading

  No Lecture (Holi)
  

  References:

  None

  • Meeting 36 : Tue, Mar 18, 08:00 am-09:00 am -

  NC1 subseteq L. Parallel vs Sequential Computation (NC vs P/poly): The circuit valuation problem (CVP). CVP is P-complete.

  References	[Vollmer] Sections 1.2 and 1.3.
  Exercises
  Reading	Limits to Parallel Computation: P Completeness, a <a href="https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf"> book</a> by Greenlaw, Hoover and Ruzzo. This book provides a good account on the theory of P completeness.

  NC1 subseteq L. Parallel vs Sequential Computation (NC vs P/poly): The circuit valuation problem (CVP). CVP is P-complete.
  

  References:	[Vollmer] Sections 1.2 and 1.3.
  Reading:	Limits to Parallel Computation: P Completeness, a book by Greenlaw, Hoover and Ruzzo. This book provides a good account on the theory of P completeness.

  • Meeting 37 : Thu, Mar 20, 11:00 am-11:50 am -

  Circuits for specific functions: ADD, ITADD, BITCOUNT, Threshold, Majority. Alternating hierarichy: AC0, AC1...

  References	[Vollmer]
  Exercises
  Reading

  Circuits for specific functions: ADD, ITADD, BITCOUNT, Threshold, Majority. Alternating hierarichy: AC0, AC1...
  

  References:

  [Vollmer]

  • Meeting 38 : Fri, Mar 21, 10:00 am-10:50 am -

  Constant depth reductions. ITADD, MAJ, and BITCOUNT are equivalent under cd-reductions.

  References	Section 1.4 in [Vollmer]. <a href="http://www.cs.au.dk/~arnsfelt/CT08/scribenotes/lecture8.pdf"> Notes </a> by Kristoffer Hansen also has a nice exposition.
  Exercises
  Reading

  Constant depth reductions. ITADD, MAJ, and BITCOUNT are equivalent under cd-reductions.
  

  References:

  Section 1.4 in [Vollmer]. Notes by Kristoffer Hansen also has a nice exposition.

  • Meeting 39 : Mon, Mar 24, 08:00 am-08:50 am -

  Threshold circuits: classes TC^i. Parity vs AC0. Introduction to lowerbounds. Lowerbound techniques: gate elimination method.

  References	[Volllmer] Book.
  Exercises
  Reading

  Threshold circuits: classes TC^i. Parity vs AC0. Introduction to lowerbounds. Lowerbound techniques: gate elimination method.
  

  References:

  [Volllmer] Book.

  • Meeting 40 : Tue, Mar 25, 12:00 pm-12:50 pm -

  Formulas. Formulas vs circuits. F=NC1. Lower bounds against formulas.

  References	[Jukna] Sections 6.1 and 6.2
  Exercises
  Reading

  Formulas. Formulas vs circuits. F=NC1. Lower bounds against formulas.
  

  References:

  [Jukna] Sections 6.1 and 6.2

  • Meeting 41 : Thu, Mar 27, 11:00 am-11:50 am -

  Sabbatovskaya's method of restrictions. Random restrictions.

  References	[Jukna] Sections 6.3 and 6.4
  Exercises
  Reading

  Sabbatovskaya's method of restrictions. Random restrictions.
  

  References:

  [Jukna] Sections 6.3 and 6.4

  • Meeting 42 : Fri, Mar 28, 10:00 am-10:50 am -

  Andreev's cubic lower bound for parity.

  References	Sections 6.4 and 12.1 in [Jukna]
  Exercises
  Reading

  Andreev's cubic lower bound for parity.
  

  References:

  Sections 6.4 and 12.1 in [Jukna]

  • Meeting 43 : Tue, Apr 01, 12:00 pm-12:50 pm -

  Constant depth Circuits. Hastad Switching lemma. Parity is not in AC0.

  References	[Jukna] Section 12.2
  Exercises
  Reading

  Constant depth Circuits. Hastad Switching lemma. Parity is not in AC0.
  

  References:

  [Jukna] Section 12.2

  • Meeting 44 : Thu, Apr 03, 11:00 am-11:50 am -

  Proof of Switching Lemma.

  References	[Jukna] Sections 12.2 and 12.3
  Exercises
  Reading

  Proof of Switching Lemma.
  

  References:

  [Jukna] Sections 12.2 and 12.3

  • Meeting 45 : Fri, Apr 04, 10:00 am-10:50 am -

  Proof of switching lemma (contd). The polynomial method: Smolensky's method of approximations.

  References	<a href="http://users-cs.au.dk/arnsfelt/CT08/scribenotes/lecture10.pdf"> Notes </a> by Kristoffer Hansen.
  Exercises
  Reading

  Proof of switching lemma (contd). The polynomial method: Smolensky's method of approximations.
  

  References:

  Notes by Kristoffer Hansen.

  • Meeting 46 : Mon, Apr 07, 08:00 am-08:50 am -

  Smolensky's proof (contd)

  References
  Exercises
  Reading

  Smolensky's proof (contd)
  

  References:

  None

  • Meeting 47 : Tue, Apr 08, 12:00 pm-12:50 pm -

  Smolensky's proof (contd). Circuits with parity and Mod_p gates. ACC0 circuits. Overview of Ryan Williams' lowerbound

  References
  Exercises
  Reading

  Smolensky's proof (contd). Circuits with parity and Mod_p gates. ACC0 circuits. Overview of Ryan Williams' lowerbound
  

  References:

  None

  • Meeting 48 : Thu, Apr 10, 11:00 am-11:50 am -

  Lower bounds against ACC0. Ryan Williams' theorem. From Satisfiability algorithms to lower bounds.

  References
  Exercises
  Reading

  Lower bounds against ACC0. Ryan Williams' theorem. From Satisfiability algorithms to lower bounds.
  

  References:

  None

  • Meeting 49 : Fri, Apr 11, 10:00 am-10:50 am -

  Williams' theorem (conclusion)

  References	Notes by Thomas Holenstein. Will be sent by email to the group.
  Exercises
  Reading

  Williams' theorem (conclusion)
  

  References:

  Notes by Thomas Holenstein. Will be sent by email to the group.

  • Meeting 50 : Tue, Apr 15, 12:00 pm-01:25 pm -

  Branching Programs and Skew circuits. Programs over permutation groups and Monoids. Barrington's theorem. (Need 2 more lectures)

  References	Helenstein's notes. Also see Chapter 4 of [Vollmer] and Section 15.4 of [Jukna]
  Exercises
  Reading

  Branching Programs and Skew circuits. Programs over permutation groups and Monoids. Barrington's theorem. (Need 2 more lectures)
  

  References:

  Helenstein's notes. Also see Chapter 4 of [Vollmer] and Section 15.4 of [Jukna]

  • Meeting 51 : Tue, Apr 15, 04:40 pm-05:35 pm -

  ...

  References
  Exercises
  Reading

  ...
  

  References:

  None

  • Meeting 52 : Wed, Apr 16, 08:00 am-08:50 am -

  Barrington's theorem (contd).

  References
  Exercises
  Reading

  Barrington's theorem (contd).
  

  References:

  None

  • Meeting 53 : Wed, Apr 16, 04:40 pm-05:35 pm -

  ...

  References
  Exercises
  Reading

  ...
  

  References:

  None

• Theme 4 : Derandomization - 7 meetings

  • Meeting 54 : Thu, Apr 17, 11:00 am-11:50 am -

  Barrington's theorem (contd). The derandomization problem: P vs BPP, L vs RL. From hardness to randomness.

  References	Holenstein's lecture notes (sent to the google group)
  Exercises
  Reading

  Barrington's theorem (contd). The derandomization problem: P vs BPP, L vs RL. From hardness to randomness.
  

  References:

  Holenstein's lecture notes (sent to the google group)

  • Meeting 55 : Mon, Apr 21, 08:00 am-08:50 am -

  Nisan-Wigderson generator.

  References	Markus Blaeser's notes.
  Exercises
  Reading

  Nisan-Wigderson generator.
  

  References:

  Markus Blaeser's notes.

  • Meeting 56 : Tue, Apr 22, 12:00 pm-01:25 pm -

  Nisan-Wigderson generator (contd). Derandomization of Polynomial Identity Testing.

  References
  Exercises
  Reading

  Nisan-Wigderson generator (contd). Derandomization of Polynomial Identity Testing.
  

  References:

  None

  • Meeting 57 : Thu, Apr 24, 11:00 am-01:00 pm -

  ACIT in P implies lower bounds (Impagliazzo-Kabanets). Arithmetic circuits. Randomized space bounded computation.

  References
  Exercises
  Reading

  ACIT in P implies lower bounds (Impagliazzo-Kabanets). Arithmetic circuits. Randomized space bounded computation.
  

  References:

  None

  • Meeting 58 : Fri, Apr 25, 10:00 am-10:50 am -

  Undirected connctivity (USTCON), the class SL. Randomized Logspace(RL). USTCON is in RL. Outline of Reingold's derandomization of USTCON.

  References
  Exercises
  Reading

  Undirected connctivity (USTCON), the class SL. Randomized Logspace(RL). USTCON is in RL. Outline of Reingold's derandomization of USTCON.
  

  References:

  None

  • Meeting 59 : Mon, Apr 28, 08:00 am-08:50 am -

  Degree reduction and expanderization in log-space. Revision of graph products: direct product, path product and replacement product.

  References
  Exercises
  Reading

  Degree reduction and expanderization in log-space. Revision of graph products: direct product, path product and replacement product.
  

  References:

  None

  • Meeting 60 : Tue, Apr 29, 12:00 pm-12:50 pm -

  Brief Overview of the course. Discussion.

  References
  Exercises
  Reading

  Brief Overview of the course. Discussion.
  

  References:

  None

• Theme 5 : Interim Evaluation - 8 meetings

  • Meeting 61 : Fri, Apr 04, 11:15 am-11:30 am -

  Devakar

  References
  Exercises
  Reading

  Devakar
  

  References:

  None

  • Meeting 62 : Thu, Apr 10, 02:00 pm-02:15 pm -

  Ankit

  References
  Exercises
  Reading

  Ankit
  

  References:

  None

  • Meeting 63 : Thu, Apr 10, 02:15 pm-02:30 pm -

  Assim

  References
  Exercises
  Reading

  Assim
  

  References:

  None

  • Meeting 64 : Thu, Apr 10, 02:30 pm-02:45 pm -

  Kartik

  References
  Exercises
  Reading

  Kartik
  

  References:

  None

  • Meeting 65 : Thu, Apr 10, 02:45 pm-03:00 pm -

  Ramya

  References
  Exercises
  Reading

  Ramya
  

  References:

  None

  • Meeting 66 : Thu, Apr 10, 03:00 pm-03:15 pm -

  Preethi

  References
  Exercises
  Reading

  Preethi
  

  References:

  None

  • Meeting 67 : Thu, Apr 10, 03:15 pm-03:30 pm -

  Subin

  References
  Exercises
  Reading

  Subin
  

  References:

  None

  • Meeting 68 : Thu, Apr 10, 03:30 pm-03:45 pm -

  Saurabh

  References
  Exercises
  Reading

  Saurabh
  

  References:

  None

• Theme 6 : Presentations - 8 meetings

  • Meeting 69 : Sat, Apr 26, 09:00 am-10:00 am - Kartik Gupta

  Kartik Gupta: Unique games conjecture and hardness of approximation for optimization problems.

  References
  Exercises
  Reading

  Kartik Gupta: Unique games conjecture and hardness of approximation for optimization problems.
  

  References:

  None

  • Meeting 70 : Sat, Apr 26, 10:00 am-11:00 am - Preethi L

  Preethi L Approximating AC0 by small height decision trees & a deterministic algorithm for #AC0 SAT. RESCHEDULED

  References
  Exercises
  Reading

  Preethi L Approximating AC0 by small height decision trees & a deterministic algorithm for #AC0 SAT. RESCHEDULED
  

  References:

  None

  • Meeting 71 : Sat, Apr 26, 11:00 am-12:00 pm - Assim A

  Assim A: On the Hardness of Graph Isomorphism.

  References
  Exercises
  Reading

  Assim A: On the Hardness of Graph Isomorphism.
  

  References:

  None

  • Meeting 72 : Sat, Apr 26, 12:00 pm-01:00 pm - Saurabh Sawlani

  Saurabh Sawlani: Making non-determinism unambiguous.

  References
  Exercises
  Reading

  Saurabh Sawlani: Making non-determinism unambiguous.
  

  References:

  None

  • Meeting 73 : Sun, Apr 27, 09:00 am-10:00 am - Devakar Verma

  Devakar Verma: Tight Bounds for Monotone Switching Networks via Fourier Analysis.

  References
  Exercises
  Reading

  Devakar Verma: Tight Bounds for Monotone Switching Networks via Fourier Analysis.
  

  References:

  None

  • Meeting 74 : Sun, Apr 27, 10:00 am-11:00 am - Subin K

  Subin K: Certifying Polynomials for AC0[Parity] circuits, with applications.

  References
  Exercises
  Reading

  Subin K: Certifying Polynomials for AC0[Parity] circuits, with applications.
  

  References:

  None

  • Meeting 75 : Sun, Apr 27, 11:00 am-12:00 pm - Ramya C.

  Ramya C: Hardness-randomness trade-off for bounded depth arithmetic circuits.

  References
  Exercises
  Reading

  Ramya C: Hardness-randomness trade-off for bounded depth arithmetic circuits.
  

  References:

  None

  • Meeting 76 : Sun, Apr 27, 12:00 pm-01:00 pm - Ankit C

  Ankit C. Parameterized Complexity of Counting.

  References
  Exercises
  Reading

  Ankit C. Parameterized Complexity of Counting.
  

  References:

  None

• Theme 7 : Exams - 9 meetings

  • Meeting 77 : Thu, May 01, 08:30 am-10:00 am -

  End Semester Exam CSB 26

  References	Lectures 1-60.
  Exercises
  Reading

  End Semester Exam CSB 26
  

  References:

  Lectures 1-60.

  • Meeting 78 : Thu, May 01, 10:30 am-11:00 am -

  Assim A.

  References
  Exercises
  Reading

  Assim A.
  

  References:

  None

  • Meeting 79 : Thu, May 01, 11:00 am-11:30 am -

  Subin S

  References
  Exercises
  Reading

  Subin S
  

  References:

  None

  • Meeting 80 : Thu, May 01, 11:30 am-12:00 pm -

  Saurabh Sawlani

  References
  Exercises
  Reading

  Saurabh Sawlani
  

  References:

  None

  • Meeting 81 : Thu, May 01, 12:00 pm-12:30 pm -

  Preethi L

  References
  Exercises
  Reading

  Preethi L
  

  References:

  None

  • Meeting 82 : Thu, May 01, 12:30 pm-01:00 pm -

  Ramya C

  References
  Exercises
  Reading

  Ramya C
  

  References:

  None

  • Meeting 83 : Thu, May 01, 01:00 pm-01:30 pm -

  Kartik Gupta

  References
  Exercises
  Reading

  Kartik Gupta
  

  References:

  None

  • Meeting 84 : Thu, May 01, 01:30 pm-02:00 pm -

  Devakar Verma

  References
  Exercises
  Reading

  Devakar Verma
  

  References:

  None

  • Meeting 85 : Thu, May 01, 02:00 pm-02:30 pm -

  Ankit C

  References
  Exercises
  Reading

  Ankit C
  

  References:

  None