- Meeting 23 : Tue, Mar 07, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Further challenges and open questions. Limitations of Probabilistic analysis. Introduction to Smoothed analysis.
- Meeting 24 : Thu, Mar 09, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis motivations and definitions. 2-OPT algorithm. Smoothed analysis of the 2-OPT algorithm. (Scribing Begins)
References: | Lecture notes by Heiko Roeglin (Chapter 6)
Also see lecture notes by Bodo Manthey (Chapter 2)
|
Reading: | 2-OPT has received wide attention in the literature. See e,g. an MSc thesis by Slotebeek about average-case analysis of 2-OPT: https://essay.utwente.nl/72060/1/Slootbeek_MA_EEMCS.pdf |
- Meeting 25 : Fri, Mar 10, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Smoothed analysis: 2-OPT (contd). The independent edge weight model. Improved bound: linked 2-exchanges.
References: | Heiko Roeglin's notes.
|
- Meeting 26 : Mon, Mar 13, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Smoothed analysis: 2-OPT (contd). Approximation ratio -- Overview of the ideas.
References: | Bodo Manthey's notes.
|
- Meeting 27 : Tue, Mar 14, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Approximation ratio of 2-OPT. Worst case bound.
References: | Original paper by Chandra et al. Check the shared google folder.
|
- Meeting 28 : Wed, Mar 15, 03:30 pm-05:00 pm
References | |
Exercises | |
Reading | |
(Lecture done on 23-03-2023, 13:45 - 15:00) Worst case bound (contd) Smoothed upper bound for the approximation ratio of 2-OPT - overview of the results.
References: | Original paper by Chandra et al. For the smoothed analysis, please refer to the thesis by Marvin Kunnemann.
|
- Meeting 29 : Thu, Mar 16, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis II: Knapsack
- Meeting 30 : Fri, Mar 17, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis II: Knapsack
- Meeting 31 : Mon, Mar 20, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis II: Knapsack
- Meeting 32 : Tue, Mar 21, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Smoothed Analysis II: Knapsack
- Meeting 33 : Thu, Mar 23, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis II: Knapsack
- Meeting 34 : Fri, Mar 24, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis III: Binary optimization
- Meeting 35 : Mon, Mar 27, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis III: Binary optimization
- Meeting 36 : Tue, Mar 28, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Smoothed analysis of 2OPT (contd) Smoothed Analysis IV: k-means clustering -- Introduction.
References: | Roeglin's notes
Manthey's notes.
|
- Meeting 37 : Wed, Mar 29, 03:30 pm-05:00 pm
References | |
Exercises | |
Reading | |
Smoothed Analysis IV: k-means clustering. Overview of the bound by Arthur and Vassilvitskii.
References: | Roeglin's notes
Manthey's notes.
|
- Meeting 38 : Thu, Mar 30, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis IV: k-means clustering. Proof of the case of dense iterations.
References: | Roeglin's notes
Manthey's notes.
|
- Meeting 39 : Fri, Mar 31, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis of k-means : Dense iterations (contd)
The sparse case.
References: | Roeglin's notes
Manthey's notes.
|
- Meeting 40 : Mon, Apr 03, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Smoothed Analysis of k-means: The sparse case (contd). Putting things together.
- Meeting 41 : Tue, Apr 11, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Smoothed Analysis and ML. Introduction to PAC learning. Fourier representations of Boolean functions.
- Meeting 42 : Wed, Apr 12, 03:30 pm-05:00 pm
References | |
Exercises | |
Reading | |
Fourier analysis and PAC learning. Learning decision trees.
- Meeting 43 : Thu, Apr 13, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Fourier analysis and PAC learning. Learning decision trees.
- Meeting 44 : Tue, Apr 18, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Fourier analysis and PAC learning. Learning decision trees.
- Meeting 45 : Wed, Apr 19, 03:30 pm-04:45 pm
References | |
Exercises | |
Reading | |
Fourier analysis and PAC learning: Decision trees (contd). Goldreich Levin Theorem.
- Meeting 46 : Thu, Apr 20, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Smoothed analysis in PAC learning: product distributions.
- Meeting 47 : Fri, Apr 21, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Smoothed analysis in other domains: Overview. Concluding remarks.
- Meeting 48 : Tue, Apr 25, 12:00 pm-01:30 pm
References | |
Exercises | |
Reading | |
Discussions : Problems and approaches.