CSE 5339 - Randomness and geometry in the design of algorithms
Instructor: Luis Rademacher.
Lectures: WeFr 3:00PM-3:55PM, BO0313
Question:
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
questions.
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.
Announcements:
Helpful courses/topics (NOT required):
The
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)).
Recommended readings:
- Randomized algorithms. R. Motwani and P. Raghavan.
- Probability and computing: randomized algorithms and probabilistic
analysis. Michael Mitzenmacher, Eli Upfal.
- An
elementary
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.
- Expander
graphs
and their applications. S.
Hoory, N. Linial,
A. Wigderson.
- Computational
Complexity: A Modern Approach. Sanjeev Arora and Boaz Barak (free
draft available).
- The random projection method. Santosh Vempala.
- Spectral Algorithms. Ravindran Kannan and Santosh Vempala. (free
preview
available)
- Geometric
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
- Convexity,
complexity
and high dimensions. Stanislaw J. Szarek.
- Faster
dimension reduction. Nir Ailon and Bernard Chazelle.
- The
fast Johnson-Lindenstrauss transform and approximate nearest neighbors.
Nir Ailon and Bernard Chazelle.
- http://people.csail.mit.edu/madhu/FT02/
lecture 2, Shannon's coding theorem.
- http://people.csail.mit.edu/ronitt/COURSE/S06/
lectures 8-9, Monte Carlo method.
Office hours:
By instructor, Dreese Labs 495, Tue 2:30-3:30pm or by appointment.
Problem Sets:
PS1 (due lecture on Mach 6th).
Grading:
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).
Topics (tentative):
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,
covariance, volume.
Complexity lower bounds. Game-theoretic techniques, Yao's min-max principle.
Introduction to the probabilistic method. Example: Shannon's theorem. Error
correcting codes. Derandomization.
Expander Graphs.
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,
VC-dimension. Extensions.