Possible course projects Please contact Adrian to discuss possible topics in more detail. If your favorite topic does not show up here, do not hesitate to suggest it. Topic Paper covered in class Reading suggestions Questions to explore Learning with experts / multiplicative weights update (MWU) Plotkin-Shmoys-Tardos Arora et al survey spectral sparsification using matrix MWU (online) mirror descent -- generalizes learning with experts weak regularity lemma using mirror descent/MWU Is there a way to obain a proof of the Szemeredi regularity lemma in this framework? Can one improve the epsilon dependence in the weak regularity lemma? Low diameter decompositions Awerbuch '83? clever scheme based on BFS with random delays low diameter decomposition for directed graphs Is there a sane/useful notion of low stretch-spanning trees that can be constructed based on this scheme? Low stretch spanning trees Alon-Karp-Peleg-West Elkin-Emek-Spielman-Teng Abraham-Bartal-Neiman Abraham-Neiman Oblivious routings & cut approximations Racke electrical flows are good oblivious routings in expander graphs Lp - oblivious routings Is there a nice way to obtain Lp oblivious routings using a similar scheme to the one we used for Linfty? What about L1 oblivious routings? How to construct L1 oblivious routings fast using j-trees? different approach for L1-oblivious routings approximate shortest path using L1-oblivious routings Madry '10 (j-trees) combines j-trees and electrical flows to obtain a fast oblivious routing scheme (see Section 4) A nice self-contained survey explaining Madry '10? Iterative methods for solving linear systems Analyze the Chebyshev iteration. Show that it indeed constructs a Chebyshev polynomial. What are the adjustments done in practice to obtain a numerically stable method? using j-trees to compute (a generalization of) electrical flows Other natural problems where j-trees can speed up algorithms? What about Lp diffusion? Spectral sparsification Spielman-Srivastava optimal spectral sparsifiers by Batson-Spielman-Srivastava speeding-up Batson-Spielman-Srivastava using a properly regularized version of MWU faster BSS sparsifiers even faster BSS sparsifiers spectral hypergraph sparsifiers (1), spectral hypergraph sparsifiers (2) sparsification for Lp norms using Lewis weights new paper on estimating effective resistances in expanders Laplacian solving Koutis-Miller-Peng theoretically fastest Laplacian system solver Can you shave off the sqrt(log n) from the running time? Laplacian solving using Schur complements Can you use vertex elimination to solve non-linear problems?