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.