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 5 ^{th}**,
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.