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