- Randomized algorithms. R. Motwani and P. Raghavan.
- 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
- An elementary introduction to modern convex geometry. Keith Ball.
- 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. 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?

- Moser, Robin A.; Tardos, Gabor (2009), A constructive proof of
the general Lovász Local Lemma, arXiv:0903.0544

http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html

http://en.wikipedia.org/wiki/Algorithmic_Lovász_local_lemma

Also, Navin's paper.

- A simple construction
of almost-Euclidean subspaces of via tensor products. Piotr Indyk,
Stanislaw Szarek

http://people.csail.mit.edu/indyk/neumann.pdf - Fast Computation of Low Rank Matrix Approximations. Dimitris Achlioptas, Frank McSherry.
- Graph Sparsification by
Effective Resistances. Daniel A. Spielman, Nikhil Srivastava

- Twice-Ramanujan Sparsifiers. Joshua Batson, Daniel A. Spielman, Nikhil Srivastava.
- Improved Approximation Algorithms for Large Matrices via Random Projections. Tamás Sarlós.
- Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions. Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp
- An Improved Approximation Algorithm for the Column Subset Selection Problem. Christos Boutsidis, Michael W. Mahoney, Petros Drineas.
- Matrix Approximation and Projective Clustering via Volume Sampling. Amit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang. (adaptive sampling)
- Adaptive Sampling and Fast Low-Rank Approximation. Amit Deshpande, Santosh Vempala.

- A New Approach to Strongly Polynomial Linear Programming. Mihaly Barasz and Santosh Vempala.
- Random walks on polytopes and an affine interior point method for linear programming. Ravi Kannan, Hariharan Narayanan.
- A Polynomial Number of Random Points does not Determine the Volume of a Convex Body. Ronen Eldan.
- Solving Convex Programs by Random Walks. D. Bertsimas, S. Vempala.
- Learning
Geometric Concepts via Gaussian Surface Area. A. Klivans, R.
O'Donnell, R. Servedio.

- A paper on computational complexity.
- Some of the topics in the list of class topics.