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.

- R. Motwani, J. Naor, and P. Raghavan,
- 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 computing, (STOC'05) - 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.

- Jittat Fakcharoenphol, Satish Rao, Kunal Talwar,
- 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.), PWS, 1996. - 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).

- Mark Jerrum and Alistair Sinclair,
- Applications of Probabilistic method in graph coloring
(the Psuedo-random coloring method).

See me for some references. - Streaming
- 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.

- Goedel Prize winning paper by Alon, Matias, Szegedy,
- 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.

- N. Alon, A. Bar Noy, N. Linial and D. Peleg,
- Property testing
- O. Goldreich, S. Goldwasser and D. Ron,

__"Property testing and its connection to learning and approximation".__

JACM, 1998. - Dana Ron,

__"Property testing",__

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)

- O. Goldreich, S. Goldwasser and D. Ron,
- Volume estimation
- Martin Dyer, Alan Frieze, Ravi Kannan,

__"A random polynomial-time algorithm for approximating the volume of convex bodies",__

JACM 38, pp 1-17, 1991

- Martin Dyer, Alan Frieze, Ravi Kannan,