CSE 788.01 - Topics in Randomized Algorithms

In this course we will get insight into one the greatest mysteries of computer science: Does randomization help? Randomization frequently makes algorithms faster or simpler. We will study the basic ingredients in the analysis of randomized algorithms, see some of the important examples and discuss select recent developments in randomized algorithms, with an aim towards understanding and working on some research questions. Topics will include the complexity of randomized algorithms, probabilistic inequalities, Markov chain Monte Carlo and lower bound techniques. Among the examples, there will be data analysis (the matrix approximation problem), sampling and counting of combinatorial and geometric structures, integration and convex optimization.


Depending on the number of students and interest, a combination of (some of, but not necessarily all of) homework, paper presentations and working on a research project (definitely no exams).

Recommended readings:

Helpful courses (NOT required):

A course about algorithms (such as 780) and a course about the theory of computation (such as 725).

Topics (tentative, depending on interest and background):

Randomized algorithms, basic paradigms, basic examples: primality testing, MIN-CUT. Analysis.
Complexity of randomized algorithms. RP, coRP, BPP, ZPP. BPP in P/poly (non-uniform derandomization)
Lower bounds. Yao's min-max principle.
Probabilistic tools. Concentration Inequalities. Markov, Tchebycheff, Chernoff. Examples. Azuma? Talagrand? McDiarmid?
Counting and Sampling:
    #P, Markov chains, MCMC, approximation of permanent.
    Geometric random walks. Randomized algorithms for sampling, integration, optimization, centroid, covariance. Isoperimetric inequalities.
Introduction to the probabilistic method
    Shannon's theorem. Error correcting codes.
    Derandomization. Example: Kashin decomposition (non-uniformity revisited). Connection with compressed sensing?
Expander Graphs
    Randomized and explicit constructions. The zig-zag product.
    Undirected connectivity in L.
Random projection?
Numerical linear algebra. SVD. Matrix approximation. Column subset selection.
Property testing? 

Papers/topics for presentation (tentative):

(Kelner-Madry, Farbod's paper on random spanning trees, volume-preserving random projection, Gittens-Tropp, Deshpande-Vempala, Kashin's paper on compressive sensing)

Topics by lecture (tentative):