RA: Schedule

The information below is still from the prior year 2022, so student can make a more informed course selection decision at the beginning of the semester. It will be updated accordingly during the course.

WeekDateLecture#LecturerTopicReading
118-Sep-20231KoushaIntroduction:  Testing polynomial identitiesChapter 1
20-Sep-20232KoushaIntroduction II: verifying Matrix multiplication and Karger's min-cut algorithmChapter 1
225-Sep-20233KoushaDiscrete Probability Chapter 1
27-Sep-20234KoushaDiscrete Probability IIChapter 2 and 3
302-Oct-20235Kousha(1/2)-approximation for Max-Cut, de-randomization via conditional expectationChapter 2 and 3
04-Oct-20236KoushaChernoff Bounds and applications IChapter 4
409-Oct-20237KoushaChernoff Bounds and applications IIChapter 4
11-Oct-20238KoushaBirthday paradox, and Balls in BinsChapter 5
516-Oct-20239KoushaThe Probabilistic Method IChapter 6
18-Oct-202310KoushaThe Probabilistic Method IIChapter 6
623-Oct-202311RaulMarkov Chains BasicsChapter 7

25-Oct-2023

 

12RaulMarkov Chains II: 2-SAT Randomized Algorithm Chapter 7
730-Oct-202313RaulMonte Carlo Method and DNF  Chapter 7
1-Nov-202314RaulMarkov Chain Monte Carlo and Approximate countingChapter 7
806-Nov-202315RaulMetropolis and Glauber Chapter 10
08-Nov-202316RaulTotal variation distance and coupling  Chapter 10
913-Nov-202317RaulPath Coupling Chapter 11
15-Nov-202318RaulIsing Models and Simulated Annealing Chapter 11
1020-Nov-202319KoushaThe Lovasz Local LemmaChapter 6
22-Nov-202320Kousha/RaulRevision session Markov chains 

 

 

License
All rights reserved The University of Edinburgh