Course Project

The main purpose of CPSC 536N is to bring students closer to the research frontier on the use of randomization in algorithms. Towards that goal, students must complete a course project, which is an in-depth study on a topic relevant to the coursework.


·         Read at least one research paper (possibly a few related papers)

·         Possible activities:

o   write up an improved presentation of the result (No plagiarism! I have failed a student for that before.)

o   implement the paper's method and perform some small experiments

o   try to generalize the paper’s results

o   apply the paper’s techniques in a new context, e.g., your own research area

o   compare the results of multiple research papers

·         No groups – all projects must be done individually.


Project Proposal

A brief description of the topic that you plan to study and the paper(s) that you plan to read. The length should be between one-half and one page in length.

Due: Monday March 16th, in class.


Final Project

This should be roughly ten pages in length.

This must be typeset in Latex. Projects written with a word processor will be penalized.

Due: Friday April 10th, by email.


Some suggested topics

·         Random Numerical Linear Algebra

·         (Survey) M. Mahoney. Randomized algorithms for matrices and data.

·         (Survey) N. Halko, P. Martinsson, J. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.

·         (Survey) D. Woodruff. Sketching as a tool for numerical linear algebra. FnTTCS 2014.

·         (Recent: FOCS ’14) M. Hardt. Understanding Alternating Minimization for Matrix Completion.

·         (Recent: SODA’15) C. Boutsidis, D. Garber, Z. Karnin, E. Liberty. Online Principal Component Analysis.

·         (Recent: ITCS ’15) M. Cohen, Y. Lee, C. Musco, C. Musco, R. Peng, A. Sidford. Uniform Sampling for Matrix Approximation.

·         (Recent: STOC ’15) M. Cohen, S. Elder, C. Musco, C. Musco, M. Persu. Dimensionality Reduction for k-Means Clustering and Low Rank Approximation.

·         Streaming Algorithms

·         S. Muthukrishnan. Data streams: algorithms and applications. FTTCS 2005.

·         P. Indyk, D. Woodruff. Optimal approximations of the frequency moments of data streams. STOC 2005.

·         P. Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. JACM 2006.

·         D. Kane, J. Nelson, D. Woodruff. An Optimal Algorithm for the Distinct Elements Problem. PODS 2010.

·         Streaming Graphs

·         K. Ahn, S. Guha, A. McGregor. Analyzing Graph Structure via Linear Measurements. SODA 2012.

·         K. Ahn, S. Guha, A. McGregor. Graph Sketches: Sparsification, Spanners, and Subgraphs. PODS 2012.

·         M. Kapralov. Better bounds for matchings in the streaming model. SODA 2013.

·         K. Ahn, S. Guha, A. McGregor. Spectral Sparsification in Dynamic Graph Streams. APPROX 2013.

·         M. Kapralov, S. Khanna, M. Sudan. Approximating matching size from random streams. SODA 2014.

·          (Recent: IPCO ’14) A. Chakrabarti, S. Kale. Submodular Maximization Meets Streaming: Matchings, Matroids, and More.

·         Johnson-Lindenstrauss

·         J. Matousek. On Variants of the Johnson-Lindenstrauss Transform. Random Structures and Algorithms

·         A. Dasgupta, R. Kumar, T. Sarlos. A Sparse Johnson-Lindenstrauss Transform. STOC 2010.

·         N. Ailon, E. Liberty. Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform. SODA 2011.

·         D. Kane, J. Nelson. Sparser Johnson-Lindenstrauss Transforms. SODA 2012.

·         (Recent: Unpublished) K. Larsen, J. Nelson. The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction.

·         Sparsifiers

·         A. Goel, M. Kapralov, S. Khanna. Graph sparsification via Refinement Sampling.

·         (Recent: FOCS ’14) M. Kapralov, Y. Lee, C. Musco, C. Musco, A. Sidford. Single-Pass Spectral Sparsification in Dynamic Streams.

·         (Recent: Unpublished) A. Andoni, R. Krauthgamer, D. Woodruff. The Sketching Complexity of Graph Cuts.

·         Lovasz Local Lemma

·         R. Moser, G. Tardos, A constructive proof of the general Lovasz Local Lemma, Journal of the ACM 2010.

·         K. Kolipaka, M. Szegedy. Moser and Tardos meet Lovasz. STOC 2011.

·         D. Harris, A. Srinivasan. The Moser-Tardos Framework with Partial Resampling. FOCS 2013.

·         (Recent: FOCS ’14) D. Achlioptas, F. Iliopoulos. The Lovasz Local Lemma as a Random Walk.

·         Hashing

·         R. Pagh, F. Rodler. Cuckoo hashing. Journal of Algorithms, 2004.

·         A. Pagh, R. Pagh, M. Ruzic. Linear probing with constant independence. STOC 2007.

·         M. Patrascu, M. Thorup. The Power of Simple Tabulation Hashing. STOC 2011.

·         (Recent: FOCS ’14) T. Christiani, R. Pagh. Generating k-independent variables in constant time.

·         Misc. Graph Algorithms

·         R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. FOCS 2006.

·         A. Goel, M. Kapralov, S. Khanna. Perfect Matchings in O(n log n) time in Regular Bipartite Graphs. STOC 2010.

·         N. Buchbinder, J. Naor, R. Schwartz. Simplex partitioning via exponential clocks and the multiway cut problem. STOC 2013.

·         Nearest Neighbors

·         P. Indyk. Nearest Neighbors in High-Dimensional Spaces.

·         A. Andoni, M. Datar, N. Immorlica, P. Indyk, V. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. 2006

·         A. Andoni, P. Indyk. Near-Optimal Hashing Algorithms for Near Neighbor Problem in High Dimensions. FOCS 2006.

·         (Recent: FOCS ’14) A. Abdullah, A. Andoni, R. Kannan, R. Krauthgamer. Spectral Approaches to Nearest Neighbor Search. FOCS 2014.

·         Network Coding

·         B. Haeupler. Analyzing network coding gossip made easy. STOC 2011.

·         H. Cheung, L. Lau, K. Leung. Graph connectivities, network coding, and expander graphs. FOCS 2011.

·         Submodular Functions

·         G. Calinescu, C. Chekuri, M. Pal, J. Vondrak. Maximizing a monotone submodular set function subject to a matroid constraint. SICOMP 2011.

·         N. Buchbinder, M. Feldman, J. Naor, R. Schwartz. A tight linear-time (1/2)-approximation for unconstrained submodular maximization. FOCS 2012.

·         Random Matrix Theory

·         J. Tropp. An introduction to matrix concentration inequalities.

·         J. Tropp. User-friendly tail bounds for sums of random matrices.

·         M. Rudelson, R. Vershynin. Non-asymptotic theory of random matrices: extreme singular values.

·         Dependent rounding

·         A. Srinivasan. Approximation algorithms via randomized rounding - a survey. 1999

·         R. Gandhi, S. Khuller, S. Parthasarathy, A. Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM, 2006.

·         G. Calinescu, C. Chekuri, M. Pal, J. Vondrak. Maximizing a Monotone Submodular Function Subject to a Matroid Constraint. SIAM Journal on Computing, 2011.

·         C. Chekuri, J. Vondrak, R. Zenklusen. Dependent Randomized Rounding for Matroid Polytopes and Applications. FOCS 2010.

·         N. Harvey, N. Olver. Pipage Rounding, Pessimistic Estimators and Matrix Concentration. SODA 2014.

·         Negative Dependence

·         D. Dubhashi, D. Ranjan. Balls and Bins: A Study in Negative Dependence.

·         R. Pemantle. Towards a theory of negative dependence.

·         J. Borcea, P. Branden, T. Liggett. Negative dependence and the geometry of polynomials.

·         Y. Peres, R. Pemantle. Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures.

·         Random Spanning Trees

·         A. Broder. Generating random spanning trees. FOCS 1989.

·         D. Wilson. Generating random spanning trees more quickly than the cover time. STOC 1996.

·         J. Propp, D. Wilson. How to get a perfectly random sample from a generic markov chain and generate a random spanning tree of a directed graph. Journal of Algorithms, 1998.

·         J. Kelner, A. Madry. Faster Generation of Random Spanning Trees. FOCS 2009.