הטכניון - מכון טכנולוגי לישראל Technion - Israel Institute of Technology Технион - израильский технологический институт ألتخنيون - معهد تكنولوجي لإسرائيل

02360374 - Probabilistic Methods and Algorithms 02360374 - Probabilistic Methods and Algorithms 02360374 - Probabilistic Methods and Algorithms 02360374 - Probabilistic Methods and Algorithms

חורף 2021-2022Winter 2021-2022Зима 2021-2022شتاء 2021-2022

סילבוס Syllabus Силабус خطة الدورة

Approximate schedule:

Week	Lecture	Recitation and Problem Solving Practice
1	Introduction	Variation distance
1-2	Linearity of expectation	Sum-Free subsets
2-3	Alterations	Derandomization using the method of conditional expectations
3-4	The isolating lemma	Derandomization using the method of limited independence
5	The second moment method	Applications of the second moment method
6	Large deviation inequalities	Large deviations in "rare" variables, multiplicative Chernoff bounds
6-7	Martingales	Additional martingale examples, the Poisson paradigm
8-9	The Lovász local lemma	A constructive proof of the local lemma
10	Correlation inequalities	Additional correlation inequalities, lower bound in Janson's inequality
11-12	Entropy	Shearer's inequality, applications
13	Introduction to random walks	Complementary material

Approximate homework schedule (subject to change):

Assignment	Release date	Due date
HW1	24.10	18.11
HW2	21.11	23.12
HW3	26.12	27.1
HW4	30.1	10.3