CSE 5339 - Randomness and geometry in the design of algorithms
Instructor: Luis Rademacher.
Lectures: WeFr 3:00PM-3:55PM, BO0313
Does randomization help?
In this course we will get insight into one the greatest mysteries of
computer science: Does randomization help? We will study the basic
ingredients in the design and analysis of randomized algorithms, see some of
the important examples and discuss select recent developments in randomized
algorithms, with an aim towards understanding some contemporary research
We will also discuss the use of non-obvious geometric ideas in the design of
algorithms. For example, it is helpful in the analysis of (not necessarily
geometric) data to imagine that this data lives in Euclidean space.
Topics will include the complexity of randomized algorithms, probabilistic
tools and inequalities, and lower bound techniques. Among the examples,
there will be applications to data analysis and machine learning.
Helpful courses/topics (NOT required):
following topics are helpful but not required, as we may review some of
them near the beginning of the course as needed: linear algebra,
probability, a course about algorithms (such as 6331 (formerly 780)) and
a course about the theory of computation (such as 6321 (formerly 725)).
- Randomized algorithms. R. Motwani and P. Raghavan.
- Probability and computing: randomized algorithms and probabilistic
analysis. Michael Mitzenmacher, Eli Upfal.
introduction to modern convex geometry. Keith Ball.
- Lectures on
discrete geometry. J. Matousek. In particular, chapters. 13-14.
- Concentration of measure for the analysis of randomized algorithms. D.
Dubhashi, A. Panconesi.
- The probabilistic method, N. Alon and J. Spencer.
and their applications. S.
Hoory, N. Linial,
Complexity: A Modern Approach. Sanjeev Arora and Boaz Barak (free
- The random projection method. Santosh Vempala.
- Spectral Algorithms. Ravindran Kannan and Santosh Vempala. (free
random walks: a survey. Santosh Vempala.
- How to
compute the volume in high dimension? Miklós Simonovits.
- Finding structure with
randomness: Stochastic algorithms for constructing approximate matrix
decompositions. Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp
and high dimensions. Stanislaw J. Szarek.
dimension reduction. Nir Ailon and Bernard Chazelle.
fast Johnson-Lindenstrauss transform and approximate nearest neighbors.
Nir Ailon and Bernard Chazelle.
lecture 2, Shannon's coding theorem.
lectures 8-9, Monte Carlo method.
By instructor, Dreese Labs 495, Tue 2:30-3:30pm or by appointment.
PS1 (due lecture on Mach 6th).
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).
Introduction to randomized algorithms, basic examples, MIN-CUT. Analysis.
Complexity of randomized algorithms: RP, coRP, BPP, ZPP.
Probabilistic tools. Concentration Inequalities. Markov, Tchebycheff,
Chernoff. Examples. The coupon collector's problem.
Complexity of high dimensional geometric properties: center of mass,
Complexity lower bounds. Game-theoretic techniques, Yao's min-max principle.
Introduction to the probabilistic method. Example: Shannon's theorem. Error
correcting codes. Derandomization.
Random projection. Randomized low rank matrix approximation. Principal
component analysis, Independent component analysis, related tensor methods
and applications to machine learning and data analysis.
Related topics in statistical learning: sample approximation, uniform
convergence, Glivenko-Cantelli theorem, Vapnik-Chervonenkis theory,