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