The objective is to introduce students to the probabilistic method, a fundamental and powerful technique in theoretical computer science.
The basic probabilistic method Illustration of the basic method using Ramsey numbers, Dominating sets in graphs and Hypergraph coloring (8 lectures)
First Moment Method Linearity of Expectation. Direct Examples Derandomization using conditional expectations. Alterations. Moments (10 lectures)
Second Moment Method Chebyshev inequalities, introduction to concentration. Higher moments and Chernoff bound. Dimensionality reduction. (12 lectures)
Selected topics from Lovasz Local Lemma, Correlation Inequalities, Martingales and Tight Concentration (12 lectures)
- To familiarize with various random constructions that show the existence of the required combinatorial object.
- 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.
- To familiarize with basic pseudo-random objects and derandomization techniques.
- 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.
- The Probabilistic Method by Noga Alon and Joel H. Spencer. Fourth Edition, Wiley, 2016. ISBN: 978-1-119-06195-3.
- Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press, 2013. ISBN: 9780511814075.
- Graph Colouring and the Probabilistic Method by Michael Molloy and Bruce Reed. Springer-Verlag Berlin Heidelberg, 2002. ISBN: 978-3-540-42139-9.
Proposing Faculty: Department: Computer Science and Engineering Programme: MCaM Proposing date: Approved date: Proposal type: Offerings:
- Offered in Jan-May, 2022 by Deepak Rajendraprasad