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 $(\log \log n)^{O(1)}$ factor from the running time?
Laplacian solving using Schur complements Can you use vertex elimination to solve non-linear problems?