Introduction to Theoretical Computer Science 2021

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
   

• Reading: These lecture notes by Costis Daskalakis (up to Section 3.1)

  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

• Reference:  https://panageas.github.io/teaching/  by Ioannis Panageas,
                  https://sites.google.com/view/cjin/ee539cos512 by Chi Jin.
  
• slides download: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