Recent Advances in Theory (CSE 290), Fall 2014

Wednesdays 10-11:50am
Computer Science building (EBU3B), room 4217/4258
Shachar Lovett

The seminar will follow a bi-weekly online seminar on Theoretical Computer Science (TCS+). This seminar hosts talks on recent advances in all areas of theoretical computer science. The seminar will alternate between background presented by students and viewing the online seminar. Students are expected to attend all classes, as well as present the background to one of the talks.


  1. (10/8) Mary Wootters (CMU), List-decodability of structured random codes. [paper]

  2. (10/15) Background: Udbhav Singh
  3. (10/22) Christos Papadimitriou (Berkeley), Satisfiability and Evolution. [paper]

  4. (10/29) Background: Kaave Hosseini
  5. (11/5) Thomas Rothvoss (U. Washington), Constructive discrepancy minimization. [paper]

  6. (11/12) Background: Sankeerth Rao
  7. (11/19) Bernard Haeupler (CMU), Interactive communication. [paper]

  8. (11/26) Background: Baiyu Li
  9. (12/03) Omri Weinstein (Princeton), Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis [paper]