Randomized Algorithms

Article Lecture 1: Introduction Motivating examples (fingerprinting, Karger min-cut, QuickSort, Freivalds) where a few coin flips replace heavy deterministic work at a tiny, controllable error. Article Lecture 2: Analysis of Randomized Algorithms The Markov–Chebyshev–Chernoff ladder of tail inequalities (one idea at three strengths), used to prove QuickSort is O(n log n) w.h.p. and R-Select finds the median in 2n + o(n). Article Lecture 3: Models & Complexity Classes Las Vegas vs Monte Carlo, the amplification gap that splits BPP from PP, the class zoo (RP/ZPP/PP/BPP), and why a weak δ-random source is secretly as good as a perfect one. Article Lecture 4.1: Design Methods I Catalogue of randomized-design methods; the first beats the worst case by randomizing the strategy. Paging k-hard; two-job scheduling 9/8-hard deterministically but →1 randomized; Yao's principle. Article Lecture 4.2: Design Methods II The fingerprint method — replace big objects by tiny random projections: Freivalds, Schwartz–Zippel, Karp–Rabin; then universal and perfect hashing, Tutte matrices and the Isolation Lemma. Article Lecture 4.3: Design Methods III The witness method — randomly hunt an element proving a property: primality (Fermat → Miller–Rabin → Solovay–Strassen), plus witnesses for Boolean matrix products rebuilding all-pairs shortest paths. Article 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). Article Lecture 5: Markov Chains, Random Walks & MC Sampling Memoryless random motion settling into a unique stationary distribution, made into a sampler (MCMC, Metropolis–Hastings); mixing via coupling, stopping times and expanders; sampling becomes counting. Article Lecture 6: Complexity II Randomness in the verifier: BPP low in the polynomial hierarchy (Sipser–Gács); a prover + coin-flipping verifier captures PSPACE (IP=PSPACE via arithmetization, SumCheck); and, made local, PCP. Article Lecture 7: Interactive Proofs & PCP Theorem IP = PSPACE via arithmetization and the sum-check protocol, then the PCP theorem NP = PCP[O(log n), O(1)] — proofs checkable in O(1) bits — so approximating Max-3-SAT is NP-hard. Article 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). PDF Lecture 1 rendered PDF Lecture 2 rendered PDF Lecture 3 rendered PDF Lecture 4 part2 rendered PDF Lecture 4 part3 rendered PDF Lecture 4 part4 rendered PDF Lecture 4 rendered PDF Lecture 5 rendered PDF Lecture 6 rendered PDF Lecture 7 rendered PDF Lecture 8 rendered