CO 759: Approximation Algorithms and Hardness of Approximation

Back home

Course Information

Institution: University of Waterloo
Dates: Spring 2024
Time: Tuesdays and Thursdays, 12:00pm-1:20pm
Room: MC 4044

Assignments

HW1
HW2

Topics and References

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