Institution: University of Waterloo
Dates: Spring 2024
Time: Tuesdays and Thursdays, 12:00pm-1:20pm
Room: MC 4044
Part I: CSPs and Approximation Algorithms based on Convex Programming
Set-Cover, Max-SAT, Max-Cut
PSD Grothendieck Inequality, Grothendieck's Inequality
Optimal Rounding for Grothendieck's Inequality
Optimal Rounding for every GCSP (Chapters 4,5,10 of Prasad Raghavendra's thesis)
Part II: Algebraic Proof of PCP Theorem (with logarithmic queries) via Tensor Codes
Dor Minzer's Notes on PCP
Dor Minzer's Notes on Sum-Check Protocol
Dor Minzer's Notes on Low-Degree Testing
Local Testing of General Tensor Codes
Part III: Composing PCPs with local gadgets to prove hardness of specific problems
Dor Minzer's PCP Course Notes
Prasad Raghavendra's thesis