Course Project

The main purpose of CO 750 is to bring students closer to the research frontier on the use of randomness in computation. 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.


Some suggested topics

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

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

ˇ         Derandomizing Randomized Rounding

ˇ         P. Raghavan. Probabilistic construction of deterministic algorithms: Approximating Packing Integer Programs. JCSS, 1988.

ˇ         N. Young. Randomized rounding without solving the linear program. SODA 1995

ˇ         Applications of Schwartz-Zippel

ˇ         S. Saraf, M. Sudan. Improved lower bound on the size of Kakeya sets over finite fields. 2008.

ˇ         Z.  Dvir, S. Kopparty, S. Saraf, M. Sudan. Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. FOCS 2009.

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

ˇ         Hashing

ˇ         M. Patrascu, M. Thorup. The Power of Simple Tabulation Hashing.

ˇ         R. Pagh, F. Rodler. Cuckoo hashing. JAlg, 2004.

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

ˇ         M. Goodrich, M. Mitzenmacher. Invertible Bloom Lookup Tables. 2011.

ˇ         Johnson-Lindenstrauss

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

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

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

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

ˇ         Nearest Neighbors

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

ˇ         Expanders

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

ˇ         Random Walks

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

ˇ         Pseudorandom Generators

ˇ         M. David, P. Papakonstantinou, A. Sidiropoulos. How strong is Nisan's pseudorandom generator?. Manuscript, 2010.

ˇ         Optimization

ˇ         J. Dunagan, S. Vempala. A simple polynomial-time rescaling algorithm for solving linear programs. Math Programming 2008.

ˇ         Discrepancy

ˇ         J. Spencer. Six standard deviations suffice. See Alon & Spencer, Ch 12 (in 2nd Ed) or Ch 13 (in 3rd Ed)

ˇ         N. Bansal, Constructive Algorithms for Discrepancy Minimization, FOCS 2010.

ˇ         Balls and Bins

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

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

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

ˇ         Rapidly Mixing Markov Chains

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

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

ˇ         Integrality Gaps

ˇ         M. Andrews, J. Chuzhoy, V. Guruswami, S. Khanna, K. Talwar, L. Zhang. Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica.

ˇ         Misc

ˇ         V. Kabanets, R. Impagliazzo. Constructive Proofs of Chernoff Bounds.

ˇ         Applications in Networking

ˇ         J. Aspnes, U. Wieder. The expansion and mixing time of skip graphs, with applications. SPAA 2005.

ˇ         G. Manku, M. Naor, U. Wieder. Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, STOC 2004.