CSE 572: Randomness & Computation

This is a graduate course on randomized algorithms.

I am a Graduate Student Instructor for the Fall 2024 offering of this course under Professor Nikhil Bansal. Here’s an outline of the course content.

• Basic Algorithms (checking identities, fingerprinting and pattern matching, primality testing, randomized min-cut, graph algorithms)
• Probabilistic Method (linearity of expectation, second moment method, Chernoff bounds, Lovasz local lemma)
• Occupancy problems (balls into bins, power of two choices, hashing)
• Algorithms for big data (unbiased estimators, streaming and sketching, frequency moments, JL transform)
• Online Learning (experts, bandits, online convex optimization, stochastic gradient descent)
• Interactive Proofs (graph non-isomorphism, number of unsatisfying assignments)
• Derandomization (conditional probability, k-wise independence, pseudorandom generators)
• Random walks (hitting time, 2-SAT, 3-SAT)
• Linear Algebra (fast linear regression, spectral sparsification)
• Approximation (LP/SDP rounding, basic spectral theory and optimization)
• Complexity (PCP theorem (simpler version))