**CS 761**

**Course project**

There will be a course project which contributes 25% to the course grade. The purpose of the course project is to facilitate your research/study by acquiring a deeper understanding on a specific topic/technique.

Students are encouraged to pick any probabilistic topic close to their research interests.

Below are some suggested projects and references.

**Concentration inequalities**- More tools and applications for concentration of measure.- D.P. Dubhashi, A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2009. (A preliminary draft available online in citeseer.)
**Local lemma**- A powerful probabilistic method made constructive in recent work.- R. Moser, G. Tardos, A constructive proof of the general Lovasz Local Lemma, Journal of the ACM, 57(2), 2010.
- K. Chandrasekaran, N. Goyal, B. Haeupler, Deterministic Algorithms for the Lova'sz Local Lemma, SODA 2010.
- B. Haeupler, B. Saha, A. Srinivasan, New Constructive Aspects of the Lova'sz Local Lemma, FOCS 2010.
**Random walks**- An important probabilistic technique with some exciting recent applications.- L. Lovasz, Random walks on graphs: a survey, 1996.
- D. Spielman, S. Teng, A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning, 2008.
- A. Goel, M. Kapralov, S. Khanna, Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs, STOC 2010.
**Randomized rounding**- Using probabilistic analysis in the design of approximation algorithms.- A. Srinivasan, Approximation algorithms via randomized rounding - a survey, Lectures on Approximation and Randomized Algorithms (M. Karonski and H. J. Promel, editors), Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN, Warszawa, pages 9-71, 1999.
- N. Young, Randomized Rounding without Solving the Linear Program, SODA 1995.
- P. Raghavan, C.D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, 7, 365-374, 1987.
**Metric embedding**- A beautiful area with elegant results and applications.- J. Matousek, Chapter 15 of Lectures on Discrete Geometry, Springer 2005.
- J. Fakcharoenphol, S. Rao, K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, 2004.
- H. Racke, Optimal Hierarchical Decompositions for Congestion Minimization in Networks, STOC 2008.
**Rapidly mixing Markov chains**- A general way to sample complicated combinatorial objects.- L. Lovász and P. Winkler, Mixing Times, Microsurveys in Discrete Probability (ed. D. Aldous and J. Propp), DIMACS Series in Discrete Math. and theor. Comp. Sci., AMS 1998, 85--133.
- M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, Birkhauser, 2003.
- M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Journal of the ACM, 51(4):671-697, 2004. (Also see chapter 11 of Motwani-Raghavan.)
- A. Frieze, E. Vigoda, A survey on the use of Markov chains to randomly sample colorings, manuscript, 2006.
**Phase transition**- A surprising phenomenon in random structures (e.g. random graphs and random SAT).- E. Friedgut, Hunting for Sharp Thresholds, Random Structures and Algorithms, 2005.
- D. Achlioptas, Random Satisfiability, Handbook of Satisfiability, 2009.
- B. Bollobas, Random Graphs, Cambridge University Press, 2001.
**Property testing**- A framework for sublinear time algorithms- O. Goldreich, Combinatorial Property Testing: Surveys and Works.
- Chapter 17 of Alon-Spencer.
**Data streaming**- An interesting area with applications in networks and databases- S. Muthukrishnan, Data Streams: Algorithms and Applications, Foundations and Trends in Theoretical Computer Science, 2005.
**Online algorithms**- A framework to analyze algorithms that make online decisions.- N. Buchbinder, J. Naor, The Design of Competitive Online Algorithms via a Primal-Dual Approach, Foundations and Trends in Theoretical Computer Science, 2009.
- A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.
- Chapter 13 of Motwani-Raghavan
**Maximum entropy distribution**- A new technique applied successfully in approximating TSP.- A. Asadpour, M. Goemans, A. Madry, S. Oveis Gharan, A. Saberi, An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem, SODA 2010.
- S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem, 2011.
**Discrepancy**- A classic topic in probabilistic method with exciting recent development.- Chapter 13 in Alon-Spencer.
- N. Bansal, Constructive Algorithms for Discrepancy Minimization, FOCS 2010.
**Other topics**- There are many other good topics...- The PCP theorem
- Communication complexity
- Pseudorandomness (e.g. chapter 9 of Alon-Spencer)
- Derandomization (e.g. chapter 16 of Alon-Spencer)
- Hashing
- Compressed sensing
- Nearest neighbor search
- Computational geometry (e.g. chapter 9 of Motwani-Raghavan)
- Graph sparsification
- Queueing theory (e.g. chapter 8 of Mitzenmacher-Upfal)
- Lower bounds for randomized algorithms
- Smoothed analysis