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. One possibility is to read a recent research paper and write up an improved presentation of the results; if you can improve the results, great! Another possibility is to develop a new algorithm that improves on the state of the art, either for a well-known problem, or for a problem relating to your research interests.


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: Tuesday February 28th, in class.


Final Project

This should be roughly ten pages in length.

Due: Thursday April 5th, in class.


Some suggested topics

·         Johnson-Lindenstrauss

·         D. Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. JCSS 2003.

·         N. Ailon, B. Chazelle. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. STOC 2006.

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

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

·         Streaming Algorithms

·         N. Alon, Y. Mathias, M. Szegedy. The Space Complexity of Approximating the Frequency Moments. JCSS 1999.

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

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

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

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

·         Approximation of Matrices

·         M. Mahoney. Randomized algorithms for matrices and data.

·         Random Matrices

·         A. Wigderson, D. Xiao. Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications.

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

·         J. Tropp. Freedman’s inequality for matrix martingales.

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

·         L. Mackey, M. Jordan, R. Chen, B. Farrell, J. Tropp. Matrix concentration inequalities via the method of exchangeable pairs.

·         Balls and Bins

·         Y. Azar, A. Broder, A. Karlin, E. Upfal. Balanced Allocations. SIAM J Comput 1999.

·         K. Talwar, U. Wieder. Balanced allocations: the weighted case. STOC 2007.

·         B. Godfrey. Balls and bins with structure: balanced allocations on hypergraphs. SODA 2008.

·         Hashing

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

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

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

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

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

·         Lovasz Local Lemma

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

·         K. Chandrasekaran, N. Goyal, B. Haeupler, Deterministic Algorithms for the Lovasz Local Lemma, SODA 2010.

·         B. Haeupler, B. Saha, A. Srinivasan, New Constructive Aspects of the Lovasz Local Lemma, FOCS 2010.

·         Random Walks

·         P. Doyle, J. L. Snell. Random walks and electric networks.

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

·         Random Trees

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

·         Property Testing

·         D. Ron. Property Testing.

·         E. Fischer. The art of uniformed decisions: A primer to property testing.

·         D. Ron. Algorithmic and analysis techniques in property testing.

·         Rapidly Mixing Markov Chains

·         L. Lovász and P. Winkler. Mixing Times, 1998.

·         L. Lovász. Random walks on graphs: a survey, 1996.

·         M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, 2003.

·         M. Jerrum, A. Sinclair. Approximating the permanent. See Motwani & Raghavan, Chapter 11.

·         M. Jerrum, A. Sinclair, E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, JACM 2004.

·         A. Frieze, E. Vigoda, A survey on the use of Markov chains to randomly sample colorings, 2006.

·         Concentration of Measure as a Geometric Phenomenon

·         M. Talagrand. A New Look at Independence. Annals of Probability, 1996.

·         A. Barvinok. Measure Concentration. 2005.

·         M. Ledoux. The Concentration of Measure Phenomenon. 2005.

·         Expanders

·         O. Reingold, S. Vadhan, A. Wigderson. Entropy waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders. Annals of Mathematics, 2002.