Note: here is a list of possible topics (followed by some suggested references)
for presentations. For each topic, you are expected to read one or two relevant papers
and present the main results in one lecture. The level of details doesn't have to
be more than the level materials were presentend
in the course.
If you want to choose onf of these topics, to know more about it, or to suggest
a new topic not listed here please talk to me.
- Randomized Rounding
- R. Motwani, J. Naor, and P. Raghavan,
Randomized Approximation Algorithms in Combinatorial Optimization,
In Approximation Algorithms for NP-hard Problems (Boston, MA, 1997), D. Hochbaum, ed., PWS Publishing, pp. 144--191.
- Approximating arbitrary metrics by tree metrics
and low-stretch spanning trees:
- Jittat Fakcharoenphol, Satish Rao, Kunal Talwar,
A tight bound on approximating arbitrary metrics by tree metrics,
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (STOC'03)
- Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng,
Lower-stretch spanning trees,
Proceedings of the thirty-seventh annual ACM symposium on Theory of
- Y. Bartal,
Probabilistic approximation of metric spaces and
its algorithmic applications,
Proceedings of the 37th Annual Symposium on
Foundations of Computer Science, p.184, October 14-16, FOCS, 1996.
- Yair Bartal,
On approximating arbitrary metrices by tree metrics,
Proceedings of the thirtieth annual ACM symposium on Theory of computing,
STOC (1998) p.161-168, May 24-26.
- Rapidly mixing markov chains
- Mark Jerrum and Alistair Sinclair,
The Markov chain Monte Carlo method: an approach to approximate
counting and integration,
A survey paper as a chapter in Approximation Algorithms for NP-hard Problems, (Dorit Hochbaum, ed.),
- Mike Molloy,
"The Glauber dynamics on the colourings of a graph with
large girth and maximum degree",
SIAM J. Computing (to appear). Conference version in Proceedings of STOC
2002. (can be downloaded from Mike's webpage)
- Alan Frieze and Eric Vigoda,
"A survey on the use of Markov chains to randomly sample colorings"
downloadable from Alan's homepage.
- M. Dyer, A. Frieze, T. Hayes and E. Vigoda
"Randomly coloring constant degree graphs",
In proceedings of FOCS (complete version downloadable from Alan's homepage).
- Applications of Probabilistic method in graph coloring
(the Psuedo-random coloring method).
See me for some references.
- Goedel Prize winning paper by Alon, Matias, Szegedy,
"The Space Complexity of Approximating the frequency moments",
in J. of computer and system sciences (JCSS), 1996.
- Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani,
"Maintaining Stream Statistics over Sliding Windows",
in SIAM J. Computing, V31(6), pp 1794-1813, 2002.
- P. Indyk, D. Woodruff,
"Optimal approximations of the frequency moments of data streams"
in Proc. of STOC 2005.
- Some of the applications of the LLL
- N. Alon, A. Bar Noy, N. Linial and D. Peleg,
On the complexity of radio communication,
Proc. 21th ACM Symp. on the Theory of Computing (STOC), Seattle, Washington, ACM Press (1989), 274-285.
- N. Alon, C. McDiarmid, B. Reed,
Acyclic coloring of graphs,
Random Structures and Algorithms, 2(3):277-288, 1991.
- U. Feige and C. Scheideler,
Improved bounds for acyclic job shop scheduling
In STOC 1998.
- Property testing
- O. Goldreich, S. Goldwasser and D. Ron,
"Property testing and its connection to learning and approximation".
- Dana Ron,
a survey downloadable from Citeseer.
- Noga Alon and Asaf Shapira,
"Every Monotone Graph Property is Testable",
in Proc. of STOC 2005, 128-137. (downloadable from Noga's webpage)
- Volume estimation
- Martin Dyer, Alan Frieze, Ravi Kannan,
"A random polynomial-time algorithm for approximating the volume of convex
JACM 38, pp 1-17, 1991