前沿算法
Final project:
Due on 10/31. Please send it to [email protected].
Together with your ID and name.
Either select any one of the papers below and summarize it. Or, pick any STOC/FOCS/SODA/SOSA paper and summarize it.
It should be a 1 page summary. More pages are okey.
- Alon Eden, Michal Feldman, Amos Fiat, Kineret Segal. An Economic-Based Analysis of RANKING for Online Bipartite Matching. SOSA 2021.
- Chandra Chekuri, Kent Quanrud, Chao Xu. LP Relaxation and Tree Packing for Minimum k-cuts. SOSA 2019.
- Thatchaphol Saranurak. A Simple Deterministic Algorithm for Edge Connectivity. SOSA 2021.
- Mohsen Ghaffari, David Wajc. Simplified and Space-Optimal Semi-Streaming for (2+ε)-Approximate Matching. SOSA 2019.
- Sepehr Assadi, Helia Yazdanyar. Simple Sublinear Algorithms for (Δ + 1) Vertex Coloring via Asymmetric Palette Sparsification. SOSA 2025.
- Josh Alman. Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables. SOSA 2023.
- Haim Kaplan, László Kozma, Or Zamir, Uri Zwick. Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps. SOSA 2019.
- Qizheng He, Zhean Xu. Simple and Faster Algorithms for Knapsack. SOSA 2024.
- Georg Anegg, Laura Vargas Koch, Rico Zenklusen. A Simple Combinatorial Algorithm for Robust Matroid Center. SOSA 2023.
- Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc. Simple and Asymptotically Optimal Online Bipartite Edge Coloring. SOSA 2024.