A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | Lec # | Date | Topic | HWs | ||||||||||||||||||||||
2 | 1/16/23 | M | MLK Day Holiday | |||||||||||||||||||||||
3 | 1 | 1/18/23 | W | Intro, Spanning trees (determinstic): O(m log* n) algo, linear time MST (randomized) | ||||||||||||||||||||||
4 | 2 | 1/20/23 | F | Min-cost arborescences and linear programs | ||||||||||||||||||||||
5 | 3 | 1/23/23 | M | Shortest paths, feasible potentials, Seidel, Fredman | HW0 due | |||||||||||||||||||||
6 | 4 | 1/25/23 | W | Shortest paths, feasible potentials, Seidel, Fredman | ||||||||||||||||||||||
7 | 5 | 1/27/23 | F | Low-diameter decompositions and Low-stretch spanning trees | ||||||||||||||||||||||
8 | 6 | 1/30/23 | M | A near-linear time algorithm for single-source shortest paths (FOCS best paper co-winner) | ||||||||||||||||||||||
9 | 7 | 2/1/23 | W | Matchings: bipartite and non-bipartite | ||||||||||||||||||||||
10 | 8 | 2/3/23 | F | Matchings via matrix methods: Tutte/Lovasz, Schwartz/Zippel, Rabin-Vazirani | HW1 | |||||||||||||||||||||
11 | 9 | 2/6/23 | M | The Matching Polytopes and Max-Weight matchings | ||||||||||||||||||||||
12 | 10 | 2/8/23 | W | The Matching Polytopes and Max-Weight matchings (part 2) | ||||||||||||||||||||||
13 | 11 | 2/10/23 | F | Concentration of Measure: Large-deviation bounds | ||||||||||||||||||||||
14 | 12 | 2/13/23 | M | Hypercube routing and Dimension Reduction | More conc? | |||||||||||||||||||||
15 | 13 | 2/15/23 | W | Dimension Reduction: random projections | ||||||||||||||||||||||
16 | 14 | 2/17/23 | F | Dimension Reduction: data streaming | HW2 | |||||||||||||||||||||
17 | 15 | 2/20/23 | M | Online Learning and the Experts Algorithm | ||||||||||||||||||||||
18 | 16 | 2/22/23 | W | Interlude: Submodularity | Guest Lecture by Madhusudhan | |||||||||||||||||||||
19 | 17 | 2/24/23 | F | online learning => zero-sum games and other applications, LPs | Sherman or Peng? | |||||||||||||||||||||
20 | 18 | 2/27/23 | M | experts for max-flow | More OCO? | |||||||||||||||||||||
21 | 19 | 3/1/23 | W | Online Learning via gradient descent, OCO | ||||||||||||||||||||||
22 | 20 | 3/3/23 | F | Mirror Descent | HW3 | |||||||||||||||||||||
23 | 3/6/23 | M | Spring Break! | |||||||||||||||||||||||
24 | 3/8/23 | W | Spring Break! | |||||||||||||||||||||||
25 | 3/10/23 | F | Spring Break! | |||||||||||||||||||||||
26 | 21 | 3/13/23 | M | Solving LPs in Poly-time (Ellipsoid, Centroid) | ||||||||||||||||||||||
27 | 22 | 3/15/23 | W | Ellipsoid, and Interior Point Methods | More IPM? | |||||||||||||||||||||
28 | 23 | 3/17/23 | F | Interior Point Methods | ||||||||||||||||||||||
29 | 24 | 3/20/23 | M | Approximation Algorithms | ||||||||||||||||||||||
30 | 25 | 3/22/23 | W | Semidefinite Programs | ||||||||||||||||||||||
31 | 26 | 3/24/23 | F | Online Algorithms | HW4 due | |||||||||||||||||||||
32 | 3/27/2023 | M | AG out of town | |||||||||||||||||||||||
33 | 3/29/2023 | W | AG out of town | |||||||||||||||||||||||
34 | 3/31/2023 | F | AG out of town | |||||||||||||||||||||||
35 | 27 | 4/3/2023 | M | SOS | ||||||||||||||||||||||
36 | 28 | 4/5/2023 | W | Martingale concentration bounds | ||||||||||||||||||||||
37 | 4/7/2023 | F | AG out of town | |||||||||||||||||||||||
38 | 29 | 4/10/2023 | M | High-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 |