Jason Li

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Congestion-Approximators from the Bottom Up.

[BibT_eX]

[DOI]

Satish Rao

Di Wang

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Unbreakable Decomposition in Close-to-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Space Complexity of Minimum Cut Problems in Single-Pass Streams.

[BibT_eX]

[DOI]

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Matroid-based TSP rounding for half-integral solutions.

[BibT_eX]

[DOI]

Math. Program., July, 2024

Low-Step Multi-commodity Flow Emulators.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Hypergraph Unreliability in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

Ruoxu Cen

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Approximating Small Sparse Cuts.

[BibT_eX]

[DOI]

Aditya Anand

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Beyond the Quadratic Time Barrier for Network Unreliability.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Deterministic Minimum Steiner Cut in Maximum Flow Time.

[BibT_eX]

[DOI]

Matthew Ding

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422).

[BibT_eX]

[DOI]

Laura Sanità

Dagstuhl Reports, 2023

A Local Search-Based Approach for Set Covering.

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Near-Linear Time Approximations for Cut Problems via Fair Cuts.

[BibT_eX]

[DOI]

Danupon Nanongkai

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.

[BibT_eX]

[DOI]

Amir Abboud

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Detecting Feedback Vertex Sets of Size k in O⋆ (2.7k) Time.

[BibT_eX]

[DOI]

Jesper Nederlof

ACM Trans. Algorithms, 2022

Optimal Bounds for the k-cut Problem.

[BibT_eX]

[DOI]

J. ACM, 2022

Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms.

[BibT_eX]

[DOI]

CoRR, 2022

Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time.

[BibT_eX]

[DOI]

Danupon Nanongkai

CoRR, 2022

Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Breaking the nk barrier for minimum k-cut on simple graphs.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Edge connectivity augmentation in near-linear time.

[BibT_eX]

[DOI]

Ruoxu Cen

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Augmenting Edge Connectivity via Isolating Cuts.

[BibT_eX]

[DOI]

Ruoxu Cen

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time.

[BibT_eX]

[DOI]

Ohad Trabelsi

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Preconditioning and Locality in Algorithm Design.

[BibT_eX]

[DOI]

PhD thesis, 2021

Gomory-Hu Tree in Subcubic Time.

[BibT_eX]

[DOI]

Ohad Trabelsi

CoRR, 2021

Breaking the nk Barrier for Minimum $k$-cut on Simple Graphs.

[BibT_eX]

[DOI]

CoRR, 2021

Approximate Gomory-Hu Tree Is Faster Than n-1 Max-Flows.

[BibT_eX]

[DOI]

CoRR, 2021

Deterministic Weighted Expander Decomposition in Almost-linear Time.

[BibT_eX]

[DOI]

CoRR, 2021

A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut.

[BibT_eX]

[DOI]

CoRR, 2021

Minimum Cuts in Directed Graphs via √n Max-Flows.

[BibT_eX]

[DOI]

CoRR, 2021

Approximate Gomory-Hu tree is faster than n - 1 max-flows.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Vertex connectivity in poly-logarithmic max-flows.

[BibT_eX]

[DOI]

Danupon Nanongkai

Sorrachai Yingchareonthawornchai

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Deterministic mincut in almost-linear time.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A quasipolynomial (2 + ε)-approximation for planar sparsest cut.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

The Connectivity Threshold for Dense Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Minimum Cuts in Directed Graphs via Partial Sparsification.

[BibT_eX]

[DOI]

Kent Quanrud

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs.

[BibT_eX]

[DOI]

Magnus Wahlström

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Tight Bound on Vertex Cut Sparsifiers in Directed Acyclic Graphs.

[BibT_eX]

[DOI]

CoRR, 2020

Optimal Bounds for the k-cut Problem.

[BibT_eX]

[DOI]

CoRR, 2020

Faster parallel algorithm for approximate shortest path.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Karger-Stein algorithm is optimal for k-cut.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Detecting Feedback Vertex Sets of Size k in O*(2.7k) Time.

[BibT_eX]

[DOI]

Jesper Nederlof

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Deterministic Min-cut in Poly-logarithmic Max-flows.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex.

[BibT_eX]

[DOI]

Sorrachai Yingchareonthawornchai

CoRR, 2019

The Number of Minimum k-Cuts: Improving the Karger-Stein Bound.

[BibT_eX]

[DOI]

CoRR, 2019

Planar diameter via metric compression.

[BibT_eX]

[DOI]

Merav Parter

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The number of minimum k-cuts: improving the Karger-Stein bound.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Distributed Computation in Node-Capacitated Networks.

[BibT_eX]

[DOI]

Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Losing Treewidth by Separating Subsets.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

On the Fixed-Parameter Tractability of Capacitated Clustering.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Tight FPT Approximations for k-Median and k-Means.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Faster Minimum k-cut of a Simple Graph.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Distributed Treewidth Computation.

[BibT_eX]

[DOI]

CoRR, 2018

Distributed Computation in the Node-Congested Clique.

[BibT_eX]

[DOI]

CoRR, 2018

Faster Distributed Shortest Path Approximations via Shortcuts.

[BibT_eX]

[DOI]

Bernhard Haeupler

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms.

[BibT_eX]

[DOI]

Mohsen Ghaffari

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Improved distributed algorithms for exact shortest paths.

[BibT_eX]

[DOI]

Mohsen Ghaffari

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

An FPT Algorithm Beating 2-Approximation for k-Cut.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Minor Excluded Network Families Admit Fast Distributed Algorithms.

[BibT_eX]

[DOI]

Bernhard Haeupler

Goran Zuzic

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Non-Preemptive Flow-Time Minimization via Rejections.

[BibT_eX]

[DOI]

Amit Kumar

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Faster Exact and Approximate Algorithms for k-Cut.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

An FPT Algorithm Beating 2-Approximation for k-Cut.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Bounding laconic proof systems by solving CSPs in parallel.

[BibT_eX]

[DOI]