Random Discrete Structures (MPI, Summer 2014)

Instructors Kunal Dutta and Arijit Ghosh

Description Study applications of randomness in computer science and combinatorics

Prerequisites Undergraduate course in algorithms and mathematical maturity

Schedule Lecture on Wednesday 10-12, Room 024, E1 4 building

Tutorial on Friday 10-12, Room 630, E1 5 building

Syllabus

Tools

  • Linearity of expectations, moments, and derivatives

  • Tail inequalities, martingales, concentration of measures
    (Markov and Chebyshev inequalities, and Chernoff type bounds)

  • Random walks, and its applications

  • Markov chains

  • Probabilistic methods

Applications

  • Metric embeddings and dimension reduction
    (Johnson-Lindenstrauss lemma, Bourgain embedding, Bartal's result)

  • Lovasz local lemma and its algorithmic results

  • Computational geometry: Randomized incremental constructions, backward analysis

  • Discrepancy

  • Dependent random choices

  • Random graphs and percolations

References

Main

  • [MU05] M. Mitzenmacher and E. Upfal, Probability and Computing, Cambridge Univ. Press, 2005.

  • [AS08] N. Alon and J. Spencer, The Probabilistic Method, 2nd ed. Wiley, 2008.

Additional

  • [MR95] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

  • [B00] B. Bollobas, Random Graphs, 2nd ed. Academic Press, 2000.

  • [JLR00] S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley, 2000.

Note that [MU05], [AS08], [MR95], [B00], and [JLR00] have been reserved in the library for this course. Online courses, lecture notes, and papers are relevant for this course.

  • [BTI04] A. Blum, Tail inequalities, CMU, 2004.

  • [BPI04] A. Blum, Probabilistic inequalities, CMU, 1998.

  • [H-P14] S. Har-Peled, Randomized Algorithms, UIUC, 2014.

  • [CL13] L. C. Lau, Randomness and Computation, CUHK, 2013.

  • [WTG10] W. T. Gowers, Two Cultures of Mathematics.

  • [RRC14] R. Rubinfeld, Randomness and Computations, MIT, 2014.

  • [SMC09] A. Sinclair, Markov Chain Monte Carlo: Foundations and Applications, UC Berkeley, 2009.

  • [SRC11] A. Sinclair, Randomness and Computation, UC Berkeley, 2011.