Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
STOC 2025
Combine vertex expander decomposition and common-neighborhood clustering for reducing the number terminals when computing vertex mincut.
Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries [pdf]
Aditya Anand, Thatchaphol Saranurak, Yunfan Wang
SODA 2025
Implement expander decomposition in the cut query model.
Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies [pdf]
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
SODA 2025
First applications of expanders to labeling schemes.
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal [pdf]
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
SODA 2025
A simple trick of increasing sink capacity can parallelize the expander decomposition algorithm.
Unbreakable Decomposition in Close-to-Linear Time [pdf]
Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, Thatchaphol Saranurak
SODA 2025
The first close-to-time algorithm for unbreakable decomposition, which is basically an expander hierarchy for small cuts.
Maximum Flow by Augmenting Paths in n^{2+o(1)} Time [pdf]
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu
FOCS 2024
Invited to SICOMP Special Issue
Introducing the directed expander hierarchy with applications to fast max flow.
Dynamic Deterministic Constant-Approximate Distance Oracles with n^ε Worst-Case Update Time [pdf]
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
FOCS 2024
Bring length-constrained expander decomposition to the dynamic setting.
Low-Step Multi-Commodity Flow Emulators [pdf] [video by Antti]
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Röyskö, Thatchaphol Saranurak
STOC 2024
Low-step shortcut that preserves both length and congestion via length-constrained expander hierarchy.
Approximating Small Sparse Cuts [pdf] [video by Aditya]
Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak
STOC 2024
Improved approximate sparsest cut for small cuts. Introduce the cut-matching game for small-set expanders.
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast [pdf]
Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak
STOC 2023
A key primitive of length-constrained expander: length-constrained max flow.
Near-Linear Time Approximations for Cut Problems via Fair Cuts [pdf]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
SODA 2023
First ~O(m)-time phi-expander decomposition algorithm (near-linear time independent of phi).
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles [pdf]
Yaowei Long, Thatchaphol Saranurak
FOCS 2022
Application of vertex-expander decomposition to the dynamic setting.
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms [pdf] [videos Gramoz, Harald, or Zihan]
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan
SODA 2021
Introducing boundary-linked expander decomposition, a very useful strengthening of expander decomposition.
Deterministic Weighted Expander Decomposition in Almost-linear Time [pdf]
Jason Li and Thatchaphol Saranurak
2021
First almost-linear time deterministic expander decomposition algorithm in general demands and weighted graphs.
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing [pdf] [video by Max and its longer version]
Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak
FOCS 2020
First application of directed expander decomposition to dynamic algorithms.
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization [pdf] [video by Yi-Jun]
Yi-jun Chang and Thatchaphol Saranurak
FOCS 2020
First deterministic distributed subpolynomial-round 1/n^{o(1)}-expander decomposition. Also, first randomized distributed polylogarithmic-round 1/polylog(n)-expander decomposition.
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond [pdf] [video]
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng and Thatchaphol Saranurak
FOCS 2020
First almost-linear time deterministic expander decomposition algorithm.
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex [pdf]
Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
2019
We observed that KKOV is useful for fast deterministic expander decomposition.
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration [pdf] [video]
Yi-Jun Chang and Thatchaphol Saranurak
PODC 2019
Best Paper Award
Invited talk at HALG 2020
First distributed subpolynomial-round 1/n^{o(1)}-expander decomposition.
Expander Decomposition and Pruning: Faster, Stronger, and Simpler [pdf] [poster] [slides]
Thatchaphol Saranurak and Di Wang
SODA 2019
First ~O(m/phi)-time phi-expander decomposition algorithm.
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time [pdf] [video@FOCS'17]
Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen
FOCS 2017
First expander pruning algorithm in n^{o(1)} update time.
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^{1/2−ε})-Time [pdf][slides][video@STOC'17]
Danupon Nanongkai and Thatchaphol Saranurak
STOC 2017
First m^{1+o(1)}-time expander decomposition algorithm.
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
STOC 2025
Use Common-Neighborhood Clustering for deterministically sparsify the max flow instances need for computing vertex mincut.
Dynamic Deterministic Constant-Approximate Distance Oracles with n^ε Worst-Case Update Time [pdf]
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
FOCS 2024
Localize length-constrained maximum flow in [HHS]
Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time [pdf]
Kevin Hua, Daniel Li, Jaewoo Park, Thatchaphol Saranurak
ICALP 2024
Localize Cheriyan and Thurimella's algorithm for listing shredders using local Ford-Fulkerson.
Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time [pdf another pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
FOCS 2023
Sublinear (1+eps)-approximate matching in subquadratic time and application to dynamic algorithms.
Sublinear Algorithms for (1.5+epsilon)-Approximate Matching [pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
STOC 2023
Sublinear (1.5+eps)-approximate matching in subquadratic time and application to dynamic algorithms.
Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction [pdf] [video by Chaitanya]
Chaitanya Nalam, Thatchaphol Saranurak
SODA 2023
Localize Karger's random contraction for minimum cuts.
Fully Dynamic Exact Edge Connectivity in Sublinear Time [pdf]
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
SODA 2023
Compute a non-trivial global mincut sparsifier in ~O(n) time on dynamic graphs.
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time [pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
SODA 2023
Best Paper Award
Invited to TALG Special Issue
Invited talk at HALG 2024
Apply sublinear algorithm maximal matching to improve dynamic matching algorithms (also see Soheil's independent work)
Deterministic Small Vertex Connectivity in Almost Linear Time [pdf] [video by SY]
Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
FOCS 2022
Sparsify max flow instances for vertex connectivity using mimicking networks.
Vertex Connectivity in Poly-logarithmic Max-flows [pdf] [video by SY]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
STOC 2021
Sparsify max flow instances for vertex connectivity to sublinear size. Use sparse recovery to construct them in sublinear time.
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms [pdf] [slides] [video@TCS+ (before merging)]
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang and Sorrachai Yingchareonthawornchai
SODA 2020
Localize a randomized version of Ford-Fulkerson flow algorithm for faster vertex connectivity.
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme [pdf]
Danupon Nanongkai, Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai
STOC 2019
Localize Dinitz's blocking flow and Goldberg-Rao flow algorithms for faster vertex connectivity.
Expander Decomposition and Pruning: Faster, Stronger, and Simpler [pdf] [poster] [slides]
Thatchaphol Saranurak and Di Wang
SODA 2019
First local algorithms for expander pruning with polylogarithmic overhead.
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time [pdf] [video@FOCS'17]
Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen
FOCS 2017
First local algorithms for expander pruning with subpolynomial overhead.
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^{1/2−ε})-Time [pdf][slides][video@STOC'17]
Danupon Nanongkai and Thatchaphol Saranurak
STOC 2017
Using deterministic sparse recovery for dynamic graph algorithms.
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time
Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
FOCS 2023
Extension of decremental SSSP for faster Gomory-Hu trees.
Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k [pdf]
Thatchaphol Saranurak, Wuwei Yuan
ESA 2023
Dynamic pairwise k-edge-connectivity for faster maximal k-edge-connected subgraphs.
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time [pdf] [tutorial video] [video by Aaron]
Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak
FOCS 2021
Decremental SSSP for faster approximate min-cost flow.
Minimum Cost Flows, MDPs, and ℓ1-Regression in Nearly Linear Time for Dense Instances [pdf]
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang
STOC 2021
Dynamic spectral data structures for faster robust IPM.
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs [pdf] [video by Jan]
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang
FOCS 2020
Invited to SICOMP special issue
Dynamic spectral data structures for faster robust IPM.
Dynamic Deterministic Constant-Approximate Distance Oracles with n^ε Worst-Case Update Time [pdf]
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
FOCS 2024
Dynamize the length-constrained expander hierarchy.
Chasing Positive Bodies [pdf]
Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak
FOCS 2023
Apply the multiplicative weight update to work in the fully dynamic setting.
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates [pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
SODA 2023
Apply the multiplicative weight update to work in the partially dynamic setting.
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers [pdf] [video by Gramoz]
Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, Thatchaphol Saranurak
FOCS 2020
Blackbox reduction from vertex sparsifiers (supporting add-terminal operation) to fully dynamic algorithms.
Sensitive Distance and Reachability Oracles for Large Batch Updates [pdf]
Jan van den Brand and Thatchaphol Saranurak
FOCS 2019
Bring the kernel basis decomposition into the dynamic setting.
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds [pdf]
Jan van den Brand, Danupon Nanongkai and Thatchaphol Saranurak
FOCS 2019
Conditionally optimal dynamic matrix inverse.
Fast Incremental Algorithms via Local Sparsifiers [pdf]
Gramoz Goranci, Monika Henzinger and Thatchaphol Saranurak
2018
Given fast static vertex sparsifiers, we obtain fast incremental algorithms.
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^{1/2−ε})-Time [pdf][slides][video@STOC'17]
Danupon Nanongkai and Thatchaphol Saranurak
STOC 2017
Bring expander decomposition into fully dynamic graph algorithms (see also independent work by Wulff-Nilsen)
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
STOC 2025
We use EDCS and decremental perfect matching in bipartite graphs with degree gaps to get the first sublinear dynamic maximal matching against an adaptive adversary.
Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary [pdf]
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert.
ESA 2022
Simpler application of the proactive resampling technique.
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary [pdf]
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
ICALP 2022
Introduce the proactive resampling technique that works against an adaptive adversary.
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds [pdf]
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer
STOC 2022
Blackbox reduction to get dynamic algorithms against an adaptive adversary, via differential privacy.
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time [pdf] [tutorial video] [video by Aaron]
Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak
FOCS 2021
More advanced congestion balancing. Introducing the expanderization of low diameter graphs.
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing [pdf] [video by Max and its longer version]
Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak
FOCS 2020
Introducing congestion balancing for maintaining flow against an adaptive adversary.
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^{1/2−ε})-Time [pdf][slides][video@STOC'17]
Danupon Nanongkai and Thatchaphol Saranurak
STOC 2017
Introducing expander decomposition for dynamic algorithms against an adaptive adversary.
Unbreakable Decomposition in Close-to-Linear Time [pdf]
Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, Thatchaphol Saranurak
SODA 2025
Application of minimum isolating cuts: single source vertex mincuts and unbreakable decomposition.
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts [pdf] [video by Zhongtian]
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
SODA 2024
The maximal version of minimum isolating cuts and its application to cactus.
Near-Linear Time Approximations for Cut Problems via Fair Cuts [pdf]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
SODA 2023
The approximation version of minimum isolating cuts and its application to approximate Gomory-Hu trees.
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time [pdf] [tutorial] [mentioned by Prasad and Oded]
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
FOCS 2022
Invited to SICOMP Special Issue
Application of minimum isolating cuts: single-source minimum cuts given "guide trees".
Optimal Vertex Connectivity Oracles [pdf] [video]
Seth Pettie, Thatchaphol Saranurak, Longhui Yin
STOC 2022
One ingredient: the element-connectivity version of minimum isolating cuts.
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs [pdf]
Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
FOCS 2021
Application of minimum isolating cuts: single-source minimum cuts for well-linked set.
Vertex Connectivity in Poly-logarithmic Max-flows [pdf] [video by SY]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
STOC 2021
One ingredient: the vertex-capacity version of minimum isolating cuts.
Tight Conditional Lower Bounds for Vertex Connectivity Problems [pdf]
Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang
STOC 2023
Tight lower bounds for combinatorial algorithms for undirected all-pairs vertex connectivity.
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates [pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
SODA 2023
SETH-hardness of fully dynamic packing/covering LPs.
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds [pdf]
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer
STOC 2022
First separation of dynamic algorithms against oblivious adversaries and adaptive adversaries.
Coarse-Grained Complexity for Dynamic Algorithms [pdf] [video by Sayan]
Sayan Bhattacharya, Danupon Nanongkai and Thatchaphol Saranurak
SODA 2020
Invited talk at HALG 2020
Analogous theory of NP-completeness for dynamic problems.
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds [pdf]
Jan van den Brand, Danupon Nanongkai and Thatchaphol Saranurak
FOCS 2019
Introduce hinted variants of the OMv conjecture.
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture [pdf] [slides@STOC'15]
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai and Thatchaphol Saranurak
STOC 2015
Introduce the OMv conjecture.
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast [pdf]
Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak
STOC 2023
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization [pdf] [video by Yi-Jun]
Yi-jun Chang and Thatchaphol Saranurak
FOCS 2020
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration [pdf] [video]
Yi-Jun Chang and Thatchaphol Saranurak
PODC 2019
Best Paper Award
Invited talk at HALG 2020
Distributed Edge Connectivity in Sublinear Time [pdf]
Mohit Daga, Monika Henzinger, Danupon Nanongkai and Thatchaphol Saranurak
STOC 2019
Distributed Exact Weighted All-Pairs Shortest Paths in O~(n^{5/4}) Rounds [pdf] [video@FOCS'17]
Chien-Chung Huang, Danupon Nanongkai and Thatchaphol Saranurak
FOCS 2017
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees [pdf] [slides] [video]
Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak
APPROX 2020
Invited to ToC special issue
Multi-finger binary search trees [pdf]
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn and Thatchaphol Saranurak
ISAAC 2018
Smooth heaps and a dual view of self-adjusting data structures [pdf] [video@STOC'18] [poster]
László Kozma and Thatchaphol Saranurak
STOC 2018
Invited to SICOMP special issue
Binary search trees and rectangulations [pdf]
László Kozma and Thatchaphol Saranurak
2016
The landscape of bounds for binary search trees [pdf]
Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, László Kozma and Thatchaphol Saranurak
2016
Pattern-avoiding Access in Binary Search Trees [pdf] [slides part 1, part 2 (by L.K.)] [video@FOCS'15]
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn and Thatchaphol Saranurak
FOCS 2015
Self-Adjusting Binary Search Trees: What Makes Them Tick? [pdf] [slides by L.K.]
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn and Thatchaphol Saranurak
ESA 2015
Greedy is an Almost Optimal Deque [pdf, slides, mentioned by David Eppstein]
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn and Thatchaphol Saranurak
WADS 2015