==== 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)       |[[https://www.irif.fr/_media/users/vladu/pst.pdf| Plotkin-Shmoys-Tardos]] | [[https://www.cs.princeton.edu/~arora/pubs/MW-survey.pdf | Arora et al survey]] | |
|   |  | [[https://arxiv.org/pdf/1107.0088.pdf | spectral sparsification using matrix MWU]] | |
|   |  | [[https://fredzhang.me/pdf/note/mirror-descent.pdf | (online) mirror descent -- generalizes learning with experts ]] | |
|   |  | [[https://lucatrevisan.wordpress.com/2019/05/16/online-optimization-post-4-regularity-lemmas/ | weak regularity lemma using mirror descent/MWU ]] | Is there a way to obain a proof of the [[https://en.wikipedia.org/wiki/Szemerédi_regularity_lemma | Szemeredi regularity lemma]] in this framework? Can one improve the epsilon dependence in the [[https://www.math.cmu.edu/~af1p/Texfiles/regular.pdf | weak regularity lemma]]? |
| Low diameter decompositions | Awerbuch '83? | [[https://arxiv.org/pdf/1307.3692.pdf | clever scheme based on BFS with random delays]] | |
|                             | | [[https://arxiv.org/pdf/2203.03456.pdf | 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  | [[https://faculty.math.illinois.edu/~west/pubs/kserver.pdf | Alon-Karp-Peleg-West]] | [[https://arxiv.org/pdf/cs/0411064.pdf | Elkin-Emek-Spielman-Teng]] | |
|   |  | [[https://arxiv.org/pdf/0808.2017.pdf | Abraham-Bartal-Neiman]] | |
|   |  | [[https://www.cs.bgu.ac.il/~neimano/spanning-full1.pdf | Abraham-Neiman]] | |
| Oblivious routings & cut approximations   | [[https://www.irif.fr/_media/users/vladu/racke.pdf | Racke]] | [[https://math.mit.edu/~kelner/publications/Electricroutingandconcurrentflowcutting.pdf | electrical flows are good oblivious routings in expander graphs ]] | |
|    |  | [[https://www.dcs.warwick.ac.uk/~englert/publications/routing_focs09.pdf | 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? |
|    |  | [[https://arxiv.org/pdf/2110.15944.pdf | different approach for L1-oblivious routings]] |  |
|    |  | [[https://arxiv.org/pdf/1911.01626.pdf | approximate shortest path using L1-oblivious routings]] | |
|    | [[https://arxiv.org/pdf/1008.1975.pdf | Madry '10 (j-trees)]] | [[https://arxiv.org/pdf/1304.2338.pdf  | 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?  |
|    |  | [[https://arxiv.org/pdf/2105.14629.pdf | 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   | [[https://arxiv.org/pdf/0803.0929.pdf | Spielman-Srivastava]] | [[https://arxiv.org/pdf/0808.0163.pdf | optimal spectral sparsifiers by Batson-Spielman-Srivastava]] |  |
|    |  | [[https://arxiv.org/pdf/1506.04838.pdf | speeding-up Batson-Spielman-Srivastava using a properly regularized version of MWU]] |  |
|    |  | [[https://arxiv.org/pdf/1508.03261.pdf | faster BSS sparsifiers]] |  |
|    |  | [[https://arxiv.org/pdf/1702.08415.pdf | even faster BSS sparsifiers]] |  |
|    |  | [[https://arxiv.org/pdf/2209.04539.pdf | spectral hypergraph sparsifiers (1)]], [[https://arxiv.org/pdf/2209.10539.pdf | spectral hypergraph sparsifiers (2)]] |  |
|    |  | [[https://arxiv.org/pdf/1412.0588.pdf  | sparsification for Lp norms using Lewis weights]] | | 
|    |  | [[https://arxiv.org/pdf/2211.01468.pdf | new paper on estimating effective resistances in expanders]] | |
| Laplacian solving   | [[https://arxiv.org/pdf/1102.4842.pdf| Koutis-Miller-Peng]] | [[https://arxiv.org/pdf/2011.08806.pdf | theoretically fastest Laplacian system solver]] | Can you shave off the $(\log \log n)^{O(1)}$ factor from the running time? |
|    |  | [[https://arxiv.org/abs/1506.08204 | Laplacian solving using Schur complements]] | Can you use vertex elimination to solve non-linear problems? |