ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
Lec #DateTopicHWs
2
1/16/23MMLK Day Holiday
3
11/18/23WIntro, Spanning trees (determinstic): O(m log* n) algo, linear time MST (randomized)
4
21/20/23FMin-cost arborescences and linear programs
5
31/23/23MShortest paths, feasible potentials, Seidel, FredmanHW0 due
6
41/25/23WShortest paths, feasible potentials, Seidel, Fredman
7
51/27/23FLow-diameter decompositions and Low-stretch spanning trees
8
61/30/23MA near-linear time algorithm for single-source shortest paths (FOCS best paper co-winner)
9
72/1/23WMatchings: bipartite and non-bipartite
10
82/3/23FMatchings via matrix methods: Tutte/Lovasz, Schwartz/Zippel, Rabin-VaziraniHW1
11
92/6/23MThe Matching Polytopes and Max-Weight matchings
12
102/8/23WThe Matching Polytopes and Max-Weight matchings (part 2)
13
112/10/23FConcentration of Measure: Large-deviation bounds
14
122/13/23MHypercube routing and Dimension ReductionMore conc?
15
132/15/23WDimension Reduction: random projections
16
142/17/23FDimension Reduction: data streamingHW2
17
152/20/23MOnline Learning and the Experts Algorithm
18
162/22/23WInterlude: Submodularity Guest Lecture by Madhusudhan
19
172/24/23Fonline learning => zero-sum games and other applications, LPsSherman or Peng?
20
182/27/23Mexperts for max-flowMore OCO?
21
193/1/23WOnline Learning via gradient descent, OCO
22
203/3/23FMirror DescentHW3
23
3/6/23MSpring Break!
24
3/8/23WSpring Break!
25
3/10/23FSpring Break!
26
213/13/23MSolving LPs in Poly-time (Ellipsoid, Centroid)
27
223/15/23WEllipsoid, and Interior Point MethodsMore IPM?
28
233/17/23FInterior Point Methods
29
243/20/23MApproximation Algorithms
30
253/22/23WSemidefinite Programs
31
263/24/23FOnline AlgorithmsHW4 due
32
3/27/2023MAG out of town
33
3/29/2023WAG out of town
34
3/31/2023FAG out of town
35
274/3/2023MSOS
36
284/5/2023WMartingale concentration bounds
37
4/7/2023FAG out of town
38
294/10/2023MHigh-Dimemnsional Expanders and Mixing of Markov Chains
HW5 due mid-April
39
40
Dynamic algorithms (e.g., for connectivity, MSTs)
41
Min-Cut using Isolating Cuts
42
Random walks and MCMC approaches to sample matroids (using HDXs)
43
Semidefinite Programs
44
Non-convex optimization
45
Secretary and Prophets
46
Smoothed Analysis
47
Graph Sparsification?
48
Linear systems solving?
49
Submodularity?
50
Fixed-Parameter algorithms
51
Algorithmic Graph Theory: Treewidth and Planarity
52
Applications of concentration inequalities
53
Dimension Reduction: SVDs
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100