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.
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.
This should be roughly ten pages in length.
Due: Thursday April 5th, in class.
Some suggested topics
· 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
· 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.
· 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.
· 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.
· O. Reingold, S. Vadhan, A. Wigderson. Entropy waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders. Annals of Mathematics, 2002.