Course Objective:

The objective is to introduce students to the probabilistic method, a fundamental and powerful technique in theoretical computer science.

Course Contents

  1. The basic probabilistic method Illustration of the basic method using Ramsey numbers, Dominating sets in graphs and Hypergraph coloring (8 lectures)

  2. First Moment Method Linearity of Expectation. Direct Examples Derandomization using conditional expectations. Alterations. Moments (10 lectures)

  3. Second Moment Method Chebyshev inequalities, introduction to concentration. Higher moments and Chernoff bound. Dimensionality reduction. (12 lectures)

  4. Selected topics from Lovasz Local Lemma, Correlation Inequalities, Martingales and Tight Concentration (12 lectures)

Learning Outcomes

  1. To familiarize with various random constructions that show the existence of the required combinatorial object.
  2. To be able to apply the various techniques taught in the course to come up with existential and constructive proofs for the existence of various mathematical objects.
  3. To familiarize with basic pseudo-random objects and derandomization techniques.
  4. To be able to construct pseudo-random objects according to the needs of the problem and come up with efficient derandomization techniques for these objects.

Text Books:

  1. The Probabilistic Method by Noga Alon and Joel H. Spencer. Fourth Edition, Wiley, 2016. ISBN: 978-1-119-06195-3.

References

  1. Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press, 2013. ISBN: 9780511814075.
  2. Graph Colouring and the Probabilistic Method by Michael Molloy and Bruce Reed. Springer-Verlag Berlin Heidelberg, 2002. ISBN: 978-3-540-42139-9.

Past Offerings

  • Offered in Jan-May, 2022 by Deepak Rajendraprasad

Course Metadata

Item Details
Course Title Probabilistic Method
Course Code CS6003
Course Credits 3-0-0-3
Course Category PME
Proposing Faculty Jasine Babu & Krithika Ramaswamy
Approved on Senate 11 of IIT Palakkad
Course prerequisites Basic knowledge of Discrete Mathematics and Probability
Course status NEW