Mathematical Basics:
Probability theory including random variables, conditional probability, Bayes law, concentration of measure, martingales; graph theory including basic definitions, spanning trees, connectivity, cuts; linear algebra including eigenvalues, norms, elementary spectral graph theory.
Traditional and Data Centric Models of Computations
Turing machine model, RAM model, streaming, sublinear algorithms, distributed data centric models based on MapReduce and Pregel.
High Dimensional Space
High dimensional sphere, volumes of high dimensional solids, gaussians in high dimension, high dimensional point sets, Johnson-Lindenstrauss theorem.
Sampling and VC-dimension
Random walks and graph sampling, MCMC algorithms, learning, linear and non-linear separators, VC-dimension and connection to sampling, PAC learning.
Sketching and Sparsification
Locality sensitive hashing, min-wise hashing, Bloom filters, count-min sketches, compressed sensing, graph sparsification techniques, pseudo-random generators with application to approximating norms.
Communication Complexity
Model, fooling sets, equality, disjointness, hardness reductions for problems in streaming, distributed verification, and property testing.
