CS6850 - Topics in Complexity Theory

Meetings  

• Theme 1 : Communication Complexity - 11 meetings

  • Meeting 01 : Fri, Jan 17, 02:00 pm-04:00 pm

  Introduction. Administrative announcements. Two party model for communication. Protocol tree. Notion of rectangles.

  References
  Exercises
  Reading

  Introduction. Administrative announcements. Two party model for communication. Protocol tree. Notion of rectangles.
  

  References:

  None

  • Meeting 02 : Wed, Jan 22, 02:00 pm-04:00 pm

  Lower bounds using monochromatic rectangles. Balancing a protocol tree. Fooling sets.

  References
  Exercises
  Reading

  Lower bounds using monochromatic rectangles. Balancing a protocol tree. Fooling sets.
  

  References:

  None

  • Meeting 03 : Fri, Jan 24, 02:00 pm-04:00 pm

  Lower bound using rank of the communication matrix.

  References
  Exercises
  Reading

  Lower bound using rank of the communication matrix.
  

  References:

  None

  • Meeting 04 : Wed, Jan 29, 02:00 pm-04:00 pm

  More on rank of the communication matrix. Log rank conjecture. Current status of the problem.

  References	[Rao-Yehudayoff]
  Exercises
  Reading

  More on rank of the communication matrix. Log rank conjecture. Current status of the problem.
  

  References:

  [Rao-Yehudayoff]

  • Meeting 05 : Fri, Jan 31, 02:00 pm-04:00 pm

  An improved upper bound for the communication complexity in terms of rank (Lovett).

  References
  Exercises
  Reading

  An improved upper bound for the communication complexity in terms of rank (Lovett).
  

  References:

  None

  • Meeting 06 : Wed, Feb 05, 02:00 pm-04:00 pm

  Lovett's theorem (contd).

  References
  Exercises
  Reading

  Lovett's theorem (contd).
  

  References:

  None

  • Meeting 07 : Fri, Feb 07, 02:00 pm-04:00 pm

  Randomized Communication Complexity.

  References
  Exercises
  Reading

  Randomized Communication Complexity.
  

  References:

  None

  • Meeting 08 : Wed, Feb 12, 02:00 pm-04:00 pm

  Randomized Communication Complexity

  References
  Exercises
  Reading

  Randomized Communication Complexity
  

  References:

  None

  • Meeting 09 : Fri, Feb 14, 02:00 pm-04:00 pm

  Number on the forehead

  References
  Exercises
  Reading

  Number on the forehead
  

  References:

  None

  • Meeting 10 : Wed, Feb 19, 02:00 pm-04:00 pm

  Lecture cancelled - -To be compensated

  References
  Exercises
  Reading

  Lecture cancelled - -To be compensated
  

  References:

  None

  • Meeting 11 : Fri, Feb 21, 02:00 pm-04:00 pm

  Number on the forehead: Lower bounds.

  References
  Exercises
  Reading

  Number on the forehead: Lower bounds.
  

  References:

  None

• Theme 2 : Circuit Complexity - 17 meetings

  • Meeting 12 : Wed, Feb 26, 02:00 pm-04:00 pm

  Circuit Complexity: Model and basic definitions

  References
  Exercises
  Reading

  Circuit Complexity: Model and basic definitions
  

  References:

  None

  • Meeting 13 : Fri, Feb 28, 02:00 pm-04:00 pm

  Examples. AC and NC hierarchy.

  References
  Exercises
  Reading

  Examples. AC and NC hierarchy.
  

  References:

  None

  • Meeting 14 : Wed, Mar 04, 02:00 pm-04:00 pm

  More examples. Formulas vs circuits. Depth reduction,.

  References
  Exercises
  Reading

  More examples. Formulas vs circuits. Depth reduction,.
  

  References:

  None

  • Meeting 15 : Fri, Mar 06, 02:00 pm-04:00 pm

  Depth Reduction. Relationship to deterministic log-space. Introduction to Branching programs and skew circuits.

  References
  Exercises
  Reading

  Depth Reduction. Relationship to deterministic log-space. Introduction to Branching programs and skew circuits.
  

  References:

  None

  • Meeting 16 : Wed, Mar 11, 02:00 pm-04:00 pm

  Skew circuits are equivalent to BPs. BPs vs Formulas. Bounded width branching programs.

  References
  Exercises
  Reading

  Skew circuits are equivalent to BPs. BPs vs Formulas. Bounded width branching programs.
  

  References:

  None

  • Meeting 17 : Fri, Mar 13, 02:00 pm-04:00 pm

  Permutation programs. Barrington's theorem: BWBP = NC^1

  References
  Exercises
  Reading

  Permutation programs. Barrington's theorem: BWBP = NC^1
  

  References:

  None

  • Meeting 18 : Wed, Mar 18, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 01 Apr) Need for lower bound against explicit functions. 2n-4 lower bound for Th. 3(n-1) lower bound for parity.

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 01 Apr) Need for lower bound against explicit functions. 2n-4 lower bound for Th. 3(n-1) lower bound for parity.
  

  References:

  None

  • Meeting 19 : Fri, Mar 20, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 03 Apr) Formula size lower bounds: Universal functions. Method of restrictions. Lower bound for parity. Subbotovoskaya's random restriction. Andreev's lower bound.

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 03 Apr) Formula size lower bounds: Universal functions. Method of restrictions. Lower bound for parity. Subbotovoskaya's random restriction. Andreev's lower bound.
  

  References:

  None

  • Meeting 20 : Wed, Mar 25, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 03 Apr) Nechiporuk's lower bound. Bounded depth circuits. Parity is not in AC0.

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 03 Apr) Nechiporuk's lower bound. Bounded depth circuits. Parity is not in AC0.
  

  References:

  None

  • Meeting 21 : Fri, Mar 27, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 08 Apr) Hastad's switching lemma. Razborov's proof.

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 08 Apr) Hastad's switching lemma. Razborov's proof.
  

  References:

  None

  • Meeting 22 : Wed, Apr 01, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 08 Apr) Polynomial method for circuit lower bounds. Representing Boolean functions as polynomials. Approximating Boolean functions by polynomials of low degree. Low degree approximation of constant depth circuits.

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 08 Apr) Polynomial method for circuit lower bounds. Representing Boolean functions as polynomials. Approximating Boolean functions by polynomials of low degree. Low degree approximation of constant depth circuits.
  

  References:

  None

  • Meeting 23 : Fri, Apr 03, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 10 Apr) Parity has no low degree approximation. Monotone circuits. Clique cannot be computed by polynomial size monotone circuits.

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 10 Apr) Parity has no low degree approximation. Monotone circuits. Clique cannot be computed by polynomial size monotone circuits.
  

  References:

  None

  • Meeting 24 : Wed, Apr 08, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 10 Apr) Razborov's proof of monotone circuit lower bound for clique. Razborov's proof (contd)

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 10 Apr) Razborov's proof of monotone circuit lower bound for clique. Razborov's proof (contd)
  

  References:

  None

  • Meeting 25 : Fri, Apr 10, 02:00 pm-04:00 pm

  Will be on online mode (To be delivered on 15 Apr) Threshold circuits. Examples.

  References
  Exercises
  Reading

  Will be on online mode (To be delivered on 15 Apr) Threshold circuits. Examples.
  

  References:

  None

  • Meeting 26 : Wed, Apr 15, 02:00 pm-04:00 pm

  CIrcuit Complexity and Communication Complexity: Monoton Formula lower bounds.

  References
  Exercises
  Reading

  CIrcuit Complexity and Communication Complexity: Monoton Formula lower bounds.
  

  References:

  None

  • Meeting 27 : Fri, Apr 17, 02:00 pm-04:00 pm

  Communication Complexity of Relations

  References
  Exercises
  Reading

  Communication Complexity of Relations
  

  References:

  None

  • Meeting 28 : Wed, Apr 22, 02:00 pm-04:00 pm

  Communication Complexity of Relations

  References
  Exercises
  Reading

  Communication Complexity of Relations
  

  References:

  None