14s: participating seminar in theoretical computer science

The course announcement is here. We meet on Wednesdays, 4–6, in MS 3915D.

The papers we're reading are collected here. (See also the link to Will's notes below.)

Pietro, Sam, and Anand have a nice proof of the hardness of random functions. It's here.

The current list (numbered by week) of speakers is below. Email Siddharth, Will, or me if you think this should be revised.

  1. Introduction, organizational meeting
  2. Space/time tradeoff 1 (Cobham paper): Zach
  3. Space/time tradeoff 2 (sorting): Siddharth
  4. Space/time tradeoff 3 (sorting again): Siddharth
  5. Intro to communication complexity: Will (link to notes)
  6. Communication complexity 2: Ted (notes to be posted?)
  7. Communication complexity 3: Pietro
  8. Communication complexity 4: Prabhanjan
  9. Automata theory 1: Anton
  10. Automata theory 2: Fred?