Introduction to Theoretical Computer Science 2021 @SJTU

Instructors

Pinyan Lu lu.pinyan@mail.shufe.edu.cn

Hu Fu hufu@mail.shufe.edu.cn

Zhihao Tang tang.zhihao@mail.shufe.edu.cn

Tsz Chiu Kwok kwok@mail.shufe.edu.cn

Nick Gravin nikolai@mail.shufe.edu.cn

Bundit Laekhanukit bundit@mail.shufe.edu.cn

Time

2021-02-25 ~ 2021-06-24  Thursday 16:00 - 17:40

Venue

East Middle Hall 4-102, 上海交通大学东中院4号楼102室

Program

  1. February 25: Introduction.

  2. March 4: Games, Equilibrium and von Neumann's Minimax Theorem

  3.March 11: Finishing von Neumann's Minimax Thoerem; linear programming duality

  • Reading: The rest of Costis's lecture notes above.

  • Reading (optional): These slides by Kevin Wayne for a complete proof of the strong duality theorem.

  • Reading (very optional, provided just in case there is interest in further explorations): Lecture notes by Michel Goemans for a more detailed introduction to linear programs.

  4.March 18:  Approximate Counting via Correlation Decay

  5.March 25: Introduction for Mechanism Design

  6.April 1: Spectral Graph Theory; Cheeger's Inequalities

  7.April 8: Local Graph Partitioning

  8.April 15:Optimization for Machine Learning

  9.April 22: Optimization for Machine Learning: A Stochastic Perspective

  10.April 29: Prophet_Secretary

  11.May 6: Online Matching

  12.May 13: Interactive Proof

  13.May 20: Intro to PCP