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.

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)).

- 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.

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.