Course project
There will be a course project which contributes 40% to the course grade.
The purpose of the course project is to facilitate your research/study by acquiring a deeper understanding on a specific topic/technique.
Students are encouraged to pick any probabilistic topic close to their research interests.
See 2018 project page for some suggested projects and references.
- Minimum Cuts
- Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai, Vertex Connectivity in Poly-logarithmic Max-flows, 2021.
- Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud, Minimum Cuts in Directed Graphs via Partial Sparsification, 2021.
- Minimum k-Cuts
- Ramsey Graphs
- Algorithmic Barrier for Random Graphs
- Dimitris Achlioptas, Amin Coja-Oghlan, Algorithmic barriers from phase transitions, 2008.
- Amin Coja-Oghlan, Charilaos Efthymiou, On independent sets in random graphs, 2014.
- David Gamarnik, Aukosh Jagannath, Alexander S. Wein, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, 2020.
- Fast Dimension Reduction
- Nir Ailon, Bernard Chazelle, The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, 2009.
- Daniel M. Kane, Jelani Nelson, Sparser Johnson-Lindenstrauss Transforms, 2014.
- Michael B. Cohen, T.S. Jayram, Jelani Nelson, Simple Analyses of the Sparse Johnson-Lindenstrauss Transform, 2018.
- Graph Sketching for Spanners
- Graph Streaming
- Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford, Single Pass Spectral Sparsification in Dynamic Streams, 2014.
- Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos, Fast and Space Efficient Spectral Sparsification in Dynamic Streams, 2014.
- Algorithmic Local Lemma
- Palette Sparsification
- Discrepancy Minimization
- Hypergraph Spectral Sparsification
- Directed Laplacian Solvers
- Michael B. Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations, 2018.
- AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil Vadhan, Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification, 2023.
- Cover Time
- Single Source Shortest Paths