Jan 17 | Introduction (slides), max clique in Erdos-Renyi graphs (Chap 1.2) |
Jan 24 | Greedy algorithm (1.3), planted clique model, statistical limits, (iterated) degree test (Chap 2.1-2.4) |
Jan 31 | Spectral Method and basic random matrix theory I (Chap 3-4) |
Feb 7 | Spectral Method and basic random matrix theory II (Chap 4-5) |
Feb 14 | SDP relaxation for planted clique, robustness (Chap 6.1-6.2) |
Feb 21 | Rounding of SDP, Convexified MLE (nuclear norm), planted partition model (Chap 6.3, 7.1) |
Feb 28 | Detection threshold of SBM, cycle-counting statistic, counting cycles in sparse graphs (Chap 7.1, 7.2) |
Mar 7 | Correlated recovery of sparse SBM, belief propagation and non-backtracking matrix (Chap 8.1, 9) |
Mar 14 | Spring break I 😄 |
Mar 21 | Spring break II 😂 |
Mar 28 | Belief propagation and non-backtracking matrix II (Chap 9) |
Apr 4 | SDP relaxation for exact and approximate recovery in SBM (Chap 10 and 12) |
Apr 11 | Planted Hamiltonian problem and LP relaxation (slides) |
Apr 18 | Graph matching I: IT analysis and simple algorithms (slides) |
Apr 25 | Graph matching II: spectral method and QP relaxation (slides) |
|