MaxCut
Computer science / Coursework / Randomized algorithms
Lecture 4.4: Design Methods IV
Relax an integer program to an LP/SDP, then round with coins: SetCover → O(ln n); MaxCut → Goemans–Williamson 0.878 via a random hyperplane. Then solving LP by randomization (Seidel, MSW, Clarkson).
Computer science / Coursework / Randomized algorithms
Lecture 8: Derandomization
Removing randomness while keeping the speed: enumeration, non-uniform advice, conditional probabilities with pessimistic estimators, k-wise independence, and PRGs (Nisan–Wigderson).