Randomized Algorithms

CS 761

Site menu:

• Information
• Notes
• Homework
• Project

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

CS, Waterloo.