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.