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#LecturerTopicReading118-Sep-20231KoushaIntroduction: Testing polynomial identitiesChapter 120-Sep-20232KoushaIntroduction II: verifying Matrix multiplication and Karger's min-cut algorithmChapter 1225-Sep-20233KoushaDiscrete Probability Chapter 127-Sep-20234KoushaDiscrete Probability IIChapter 2 and 3302-Oct-20235Kousha(1/2)-approximation for Max-Cut, de-randomization via conditional expectationChapter 2 and 304-Oct-20236KoushaChernoff Bounds and applications IChapter 4409-Oct-20237KoushaChernoff Bounds and applications IIChapter 411-Oct-20238KoushaBirthday paradox, and Balls in BinsChapter 5516-Oct-20239KoushaThe Probabilistic Method IChapter 618-Oct-202310KoushaThe Probabilistic Method IIChapter 6623-Oct-202311RaulMarkov Chains BasicsChapter 725-Oct-2023 12RaulMarkov Chains II: 2-SAT Randomized Algorithm Chapter 7730-Oct-202313RaulMonte Carlo Method and DNF Chapter 71-Nov-202314RaulMarkov Chain Monte Carlo and Approximate countingChapter 7806-Nov-202315RaulMetropolis and Glauber Chapter 1008-Nov-202316RaulTotal variation distance and coupling Chapter 10913-Nov-202317RaulPath Coupling Chapter 1115-Nov-202318RaulIsing Models and Simulated Annealing Chapter 111020-Nov-202319KoushaThe Lovasz Local LemmaChapter 622-Nov-202320Kousha/RaulRevision session Markov chains License All rights reserved The University of Edinburgh Book traversal links for RA: Schedule RA: Course Materials Up RA: Tutorials