Unless stated otherwise, author names are in alphabetical order.
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers [pdf]
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
Reviving Thorup's Shortcut Conjecture [pdf]
Aaron Bernstein, Henry Fleischmann, George Z. Li, Bernhard Haeupler, Maximilian Probst Gutenberg,
Gary Hoppenworth, Seth Pettie, Thatchaphol Saranurak, Yonggang Jiang, Leon Schiller
77. Reducing Shortcut and Hopset Constructions to Shallow Graphs [pdf]
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
SOSA 2026
76. Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching [pdf]
Matija Bucic, Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
SODA 2026
75. Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems [pdf]
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
SODA 2026
74. Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time [pdf]
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
SODA 2026
73. Near-Optimal Fault-Tolerant Strong Connectivity Preservers [pdf]
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang
FOCS 2025
72. Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs [pdf]
Aaron Bernstein, Joakim Blikstad, Jason Li, Thatchaphol Saranurak, Ta-Wei Tu
FOCS 2025
71. Parallel (1+ε)-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work [pdf]
Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
FOCS 2025
70. Deterministic Almost-Linear-Time Gomory-Hu Trees [pdf]
Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst, Thatchaphol Saranurak, Wuwei Yuan, Weixuan Yuan
FOCS 2025
69. Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts [pdf]
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
ESA 2025
68. All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs [pdf]
Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak
ICALP 2025
67. Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method [pdf]
Deeksha Adil, Thatchaphol Saranurak
ICALP 2025
Summary: We dynamize the power method. Maximum vector is a very special case of SDPs but not captured by LPs. So, this is a step towards dynamic SDP algorithms.
66. Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness [pdf]
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
STOC 2025
Summary: Improve the time for weighted vertex connectivity from m^2 [HRG] to mn. This breaks the trivial n^4-time bound in dense graphs for the first time. In unweighted, we get mk time, subsuming all known algorithms. New techniques: common-neighborhood clustering and pseudorandomness object such as dispersers and selectors.
65. Deterministic Dynamic Maximal Matching in Sublinear Update Time [pdf]
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
STOC 2025
Invited to SICOMP Special Issue
Summary: This answers a long-standing open problem. Dynamic maximal matching admits non-trivial o(n) update time! We use EDCS in a completely new way.
64. Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries [pdf]
Aditya Anand, Thatchaphol Saranurak, Yunfan Wang
SODA 2025
Summary: First deterministic max flow and global mincut in the subquadratic cut queries.
63. Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies [pdf]
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
SODA 2025
Summary: First applications of expanders to labeling schemes.
62. Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal [pdf]
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
SODA 2025
Summary: A simple trick of increasing sink capacity can parallelize the expander decomposition algorithm.
61. Unbreakable Decomposition in Close-to-Linear Time [pdf]
Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, Thatchaphol Saranurak
SODA 2025
Summary: The first close-to-time algorithm for unbreakable decomposition, which is basically an expander hierarchy for small cuts.
60. 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
Summary: A novel approach for computing maximum flow. Two new concepts: weighted push-relabel and directed expander hierarchy.
59. Dynamic Deterministic Constant-Approximate Distance Oracles with n^ε Worst-Case Update Time [pdf]
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
FOCS 2024
Summary: First dynamic distance oracles against adaptive adversary with O(1)-approximation and sublinear update time. This paper brings length-constrained expanders into the area of dynamic algorithms.
58. Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time [pdf]
Kevin Hua, Daniel Li, Jaewoo Park, Thatchaphol Saranurak
ICALP 2024
Summary: Generalize the local flow technique for finding vertex cuts to also list shredders.
57. Low-Step Multi-Commodity Flow Emulators [pdf] [video by Antti]
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Röyskö, Thatchaphol Saranurak
STOC 2024
Summary: Introduce graph shortcuts for min-cost multi-commodity flow. How to add shortcuts so that every multi-commodity flow demand can still be routed be approximately the same congestion and length, but routed though only path with few steps (numbers of edges). This gives the first close-to-linear time O(1)-approximation algorithm for k-commodity flow for large k.
56. Approximating Small Sparse Cuts [pdf] [video by Aditya]
Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak
STOC 2024
Summary: Approximate sparse cuts within polylog(cutsize) instead of polylog(n). Two new techniques 1) sample sets for sparse cuts, 2) cut-matching game for small set expanders.
55. Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts [pdf] [video by Zhongtian]
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
SODA 2024
Summary: Introduce Maximal Isolating Mincuts with its first application: building cactus. I expect to see more applications for this tool.
54. Cactus Representation of Minimum Cuts: Derandomize and Speed up [pdf]
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
SODA 2024
Summary: A detailed and complete proof of how to construct a cactus in near-linear time. Our approach is more modular and also deterministic.
53. 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
Summary: Improve our recent ~O(n^2)-time Gomory-Hu tree algorithm to an almost-linear-time algorithm using data structures.
52. Chasing Positive Bodies [pdf]
Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak
FOCS 2023
Summary: How MWU should look like the fully dynamic setting: slick and with cool applications.
51. Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time [pdf another pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
FOCS 2023, HALG 2023 (Contributed talk)
Summary: Implement McGregor's streaming algorithm for (1+eps)-matching in the sublinear model. Key idea: implement a large matching oracle on any given induced subgraphs.
50. Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k [pdf]
Thatchaphol Saranurak, Wuwei Yuan
ESA 2023
Summary: Reducting this problem to the dynamic pairwise k-connectivity problem.
49. Sublinear Algorithms for (1.5+epsilon)-Approximate Matching [pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
STOC 2023
Summary: Implementing EDCS (edge-degree constrained subgraph) on the sublinear model to improve the approximation from (2-eps) to (1.5+eps).
48. Tight Conditional Lower Bounds for Vertex Connectivity Problems [pdf]
Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang
STOC 2023
Summary: All-pairs vertex connectivity requires n^4 time, assuming the 4-clique conjecture: a stark difference from all-pairs edge connectivity (Gomory-Hu trees).
47. Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast [pdf]
Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak
STOC 2023
Summary: Fast, parallel, deterministic algorithm for computing "short" flow. This is a basis for a theory of length-constrained expanders.
46. Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction [pdf] [video by Chaitanya]
Chaitanya Nalam, Thatchaphol Saranurak
SODA 2023
Summary: We study the localized version of Karger's random contraction technique, and its applications.
45. Fully Dynamic Exact Edge Connectivity in Sublinear Time [pdf]
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
SODA 2023
Summary: The first non-trivial fully dynamic algorithm for exact global mincut.
44. 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
Summary: The long-standing approximation ratio of 2 for dynamic matching in polylog update time can be improved to 1.98 if you want only size estimation! The techniques combines insight from streaming algorithms and sublinear algorithms.
43. Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates [pdf]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
SODA 2023
Summary: Partially dynamic packing-covering LPs in polylog(n) amortized update time. This is tight: fully dynamic or worst-case update time require n^{1-o(1)} update time. The insight about multiplicative weight update from this paper is nice in my opinion.
42. Near-Linear Time Approximations for Cut Problems via Fair Cuts [pdf]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
SODA 2023
Summary: Approximate Gomory-Hu trees and expander decomposition in O(m polylog m) time, not just m^{1+o(1)} time. There is a huge technical gap between the two regimes currently.
41. Deterministic Small Vertex Connectivity in Almost Linear Time [pdf] [video by SY]
Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
FOCS 2022, HALG 2023 (Contributed talk)
Summary: Using expander and vertex sparsifiers for deterministically computing vertex connectivity in almost-linear time. The previous bound is quadratic.
40. Near-Optimal Deterministic Vertex-Failure Connectivity Oracles [pdf]
Yaowei Long, Thatchaphol Saranurak
FOCS 2022
Summary: After deleting d vertices of a graph, we can check if vertices u and v are still connected quickly? This paper gives a near-optimal data structure for this question. Along the way, we show the first almost-linear time algorithms for computing vertex-expander decomposition and hypergraph-expander decomposition.
39. 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
Summary: Break the 60-year-old n^3-time barrier for Gomory-Hu trees (all-pairs max flows) to n^2.
38. Vertex Sparsifiers for Hyperedge Connectivity [pdf]
Han Jiang, Shang-En Huang, Thatchaphol Saranurak, Tian Zhang
ESA 2022
Summary: Generalize the cool results of these papers to hypergraphs.
37. Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary [pdf]
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert.
ESA 2022
Summary: The greedy spanner algorithm give a near optimal deterministic dynamic spanner algorithm if we only count the recourse (number of changes). We also give a streamlined argument for the general proactive resampling technique which is of independent interest.
36. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver [pdf] [video by SY]
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai
ICALP 2022
Summary: Solve LP for the k-ECSS problem in near-linear time.
35. 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
Summary: We maintain graph edge-sparsifiers in polylog(n) time against an adaptive adversary. To do this, we introduce a novel simple technique called proactive resampling as a new toolkit against adaptive adversaries.
34. Optimal Vertex Connectivity Oracles [pdf] [video]
Seth Pettie, Thatchaphol Saranurak, Longhui Yin
STOC 2022
Summary: We show that k-vertex connectivity oracles require \Omega(nk) space (unlike edge connectivity, where Gomory-Hu trees imply O(n)-space oracles). Complementing the lower bound, we speed up the known O(nk)-space oracle to have O(log n) query time, and poly(k) * max-flow construction time.
33. 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
Summary: Connect dynamic algorithms to differential privacy, cryptography, and adaptive data analysis.
32. A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs [pdf]
Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
FOCS 2021
Summary: All-pairs min-cuts in n^{2+o(1)} time (which is tight with the output size).
31. Minimum Cuts in Directed Graphs via Partial Sparsification [pdf and the old version]
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud and Thatchaphol Saranurak
FOCS 2021
Summary: Fastest directed mincut algorithm (adapting fast tree packing and sparsification to directed graphs).
30. 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
Summary: We show a near-optimal deterministic decremental algorithm for single-source shortest paths. We then use it to solve approximate min-cost flow and vertex max flow in almost-linear time.
29. Vertex Connectivity in Poly-logarithmic Max-flows [pdf] [video by SY]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
STOC 2021, HALG 2022 (Contributed talk)
Invited to SICOMP Special Issue
Summary: Exact vertex connectivity in almost max flow time. A new nice technique is to compute kernels of vertex cuts in sublinear time.
28. 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
Summary: Generalizing the technique from the previous paper to work with LPs with box constraints.
27. A Simple Deterministic Algorithm for Edge Connectivity [pdf] [video]
Thatchaphol Saranurak
SOSA 2021
Summary: Computing min cuts in a few pages.
26. Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition [pdf] [video]
Julia Chuzhoy, Thatchaphol Saranurak
SODA 2021
Summary: (1) The first deterministic single-source-shortest-paths algorithm on standard edge-decremental graphs that is faster than the classical ES-tree algorithm from 1981 and can return an approximate shortest path (not just distance estimates), and (2) the first deterministic all-pair-shortest-paths algorithm on decremental graphs that breaks the O(n^3)-time bound on dense graphs.
25. 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
Summary: We introduce the expander hierarchy as a clean combinatorial object that is very robust against adversarial updates, yet strong enough to imply the first dynamic algorithm for tree flow sparsifiers (which in turn implies first algorithms for dynamic approximate max flow and tree-width decomposition and simplification of deterministic dynamic connectivity).
24. 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
Summary: Deterministically breaking the O(mn)-bound by Even-Shiloach tree from 1981 for dynamic reachability and SCC. Our novel congestion balancing technique for maintaining flow also implies the first near-optimal algorithm for decremental bipartite matching.
23. Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization [pdf] [video by Yi-Jun]
Yi-jun Chang and Thatchaphol Saranurak
FOCS 2020
Summary: Derandomizing expander-based techniques in the CONGEST model near-optimally.
22. 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
Summary: Speeding up iterations of the interior-point method using dynamic expander decomposition.
21. 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
Summary: A new framework for dynamizing many vertex-sparsifiers with applications to dynamic cuts, distance, and effective resistances.
20. 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
Summary: The first deterministic almost-linear time for the balanced cut problem. From this, we finally resolve the major open problem of whether dynamic graph connectivity admits deterministic update time polynomially faster than O(sqrt{n}).
19. 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
Summary: Wilber 1 (w.r.t. a balanced tree) was the only approach for showing binary search trees with a non-trivial competitive ratio. We show that even a stronger version of Wilber 1 (w.r.t. the best tree) cannot yield a much better competitive ratio. (See this work for an independent result.) Additionally, we show the first subexponential-time offline algorithm for O(1)-approximating the optimal cost of binary search trees.
18. 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
Summary: The first near-linear time algorithm for computing k-vertex connectivity when k is polylog. This answers affirmatively the conjecture by Aho, Hopcroft, and Ullman since 1972 (up to log factors and when k is polylog). Our key tool is a local algorithm that also implies nice applications for property testing. This is a merge of two independent works.
17. Coarse-Grained Complexity for Dynamic Algorithms [pdf] [video by Sayan]
Sayan Bhattacharya, Danupon Nanongkai and Thatchaphol Saranurak
SODA 2020
Invited talk at HALG 2020
Summary: We develop the analogous theory of NP-completeness in the dynamic setting.
16. Sensitive Distance and Reachability Oracles for Large Batch Updates [pdf]
Jan van den Brand and Thatchaphol Saranurak
FOCS 2019
Summary: We give the first graph-algorithmic application of the kernel basis decomposition of polynomial matrices developed quite recently in the symbolic computation community.
15. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds [pdf]
Jan van den Brand, Danupon Nanongkai and Thatchaphol Saranurak
FOCS 2019, HALG 2019 (Contributed talk)
Summary: An improvement of a very powerful dynamic matrix inverse algorithm by Sankowski. We also identify a barrier which indicates that our new algorithm is optimal
14. 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
Summary: The first distributed algorithm for computing balanced sparse cuts. We use this to perform much faster expander decomposition and near-optimal triangle enumeration.
13. Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme [pdf]
Danupon Nanongkai, Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai
STOC 2019, HALG 2019 (Contributed talk)
Invited to SICOMP special issue
Summary: Breaking the 50-year-old O(n^2)-time bound for computing vertex connectivity.
12. Distributed Edge Connectivity in Sublinear Time [pdf]
Mohit Daga, Monika Henzinger, Danupon Nanongkai and Thatchaphol Saranurak
STOC 2019, HALG 2019 (Contributed talk)
Summary: We simplify previous algorithms for computing global min-cut by exploiting expander decomposition. From this simplicity and by combining with other techniques, we get the first sublinear-time distributed algorithm for computing exact global mincut.
11. Expander Decomposition and Pruning: Faster, Stronger, and Simpler [pdf] [poster] [slides]
Thatchaphol Saranurak and Di Wang
SODA 2019, HALG 2019 (Contributed talk)
Summary: The first near-linear time for (truly) decomposing graphs into expanders. The technique is based on a "dynamic" version of the local flow algorithm which is faster, stronger, and simpler than previous techniques.
10. Multi-finger binary search trees [pdf]
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn and Thatchaphol Saranurak
ISAAC 2018
Summary: Some observations on connections between three prominent topics in online algorithms: binary search trees, k-server, and multiplicative weight updates.
9. Smooth heaps and a dual view of self-adjusting data structures [pdf] [video@STOC'18] [poster]
László Kozma and Thatchaphol Saranurak
STOC 2018, HALG 2019 (Contributed talk)
Invited to SICOMP special issue
Summary: We show a general transformation between binary search trees (BSTs) and heaps, two fundamental types of data structures. This allows us to initialize the theory of dynamic optimality of heaps by transferring the rich analogous theory of BSTs. Via the connection, we discover a heap, called the smooth heap, which is very simple to implement, yet inherits most strong guarantees from BST literature, and is optimal within a natural subclass of heaps.
8. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time [pdf] [video@FOCS'17]
Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen
FOCS 2017
Summary: Improve the worst-case update time of dynamic minimum spanning forest from O(n^0.499) to less than O(n^0.001).
7. 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
Summary: The first nontrivial exact algorithm for distributed weighted all-pairs shortest paths.
6. 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, HALG 2017 (Contributed talk)
Summary: The polynomial improvement over the 20-year-old O(n^{0.5}) bound for dynamic spanning forest algorithms with worst-case update time guarantee when an adversary is adaptive.
Note: Wulff-Nilsen also independently breaks this barrier by a polynomial factor. He solves the harder problem (minimum spanning tree).
5. 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, HALG 2016 (Contributed talk)
Summary: We apply a well-studied forbidden submatrix theory to a geometric view of the execution log of Greedy, a binary search tree algorithm conjectured to be optimal. By this, we obtain linear bounds (up to a factor depending on inverse-Ackermann function) of the cost of Greedy on pattern-avoiding sequences. As a consequence, we almost resolve traversal conjecture "for Greedy". (Traversal conjecture was originally conjectured for splay tree and no non-trivial bound was known.)
4. 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
Summary: We study how a BST algorithm should adjust its search path after each access so that the algorithm has "good properties" or, to be more precise, satisfies access lemma via sum-of-log potential. We describe such rules which are purely combinatorial conditions on the structure of the search path in contrast to previous attempts. As an interesting by-product, these rules give a framework for proving access lemma for the algorithm called "depth-halving" which is previously conjectured to satisfy the lemma, and also all algorithms, e.g. splay and Greedy, which are known to satisfy it.
3. 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
Summary: (1) We extend the geometric view of binary search tree, which only considered access, to include insertion and deletion. (2) This allows us to apply the forbidden submatrix technique from our FOCS'15 paper to show that when we only insert or delete the minimum or maximum elements, i.e. execute a deque sequence, the amortized cost of Greedy is almost constant (some factor depending on inverse-Ackermann function). This gives yet another evidence that Greedy might be dynamically optimal as conjectured (like splay tree).
2. 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, HALG 2016 (Contributed talk)
Summary: It is not known how to multiply an online sequence of Boolean vectors of size n to a fixed Boolean matrix of size n*n faster than n^{2-eps} time per vector, while a trivial algorithm takes n^2 time. We propose the OMv conjecture which says that no such algorithm exists. This gives stronger and easier-to-proof conditional lower bounds of amortized update time to a dozen of dynamic problems, including both fully dynamic and partially dynamic problems, even with any polynomial preprocessing time.
1. Finding the Colors of the Secret in Mastermind [pdf]
Thatchaphol Saranurak
CTW 2013
Summary: We show how to find a secret in the game called Mastermind using few queries. Our algorithm is as good as previous algorithms but it is better when there are few colors in the secret code.
4. Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time [link]
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
J.ACM 2024
3. Pinning Down the Strong Wilber-1 Bound for Binary Search Trees [link]
Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak
ToC 2023
2. Near-optimal Distributed Triangle Enumeration via Expander Decompositions [link]
Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, Hengjie Zhang
J. ACM 2021
1. Smooth Heaps and a Dual View of Self-Adjusting Data Structures [link]
László Kozma, Thatchaphol Saranurak:
SICOMP 2020
Dynamic algorithms: new worst-case and instance-optimal bounds via new connections [link]
supervised by Danupon Nanongkai at KTH
PosSLP and The Monotone Complexity of Computing Integers [pdf]
supervised by Markus Bläser at Saarland University
Co-Winner of The Günter-Hotz Medal Summer 2014
Summary: Consider the problem called PosSLP: given an arithmetic circuit where all inputs are numbers (not variables), decide whether the number computed by it is positive or not. We show an interesting connection from this problem to the separation of the monotone vs. non-monotone complexity of computing intergers. Roughly, if there is no such separation, then we get an extremely strong upper bound for PosSLP. We also show the first non-trivial unconditional lower bound of the size of arithmetic circuits for computing some explicit number sequence. Trivial: any number x requires a circuit of size at least loglog(x), New: a number x in a sequence that encodes EXPSPACE-complete problems cannot be computed by any circuit of size poly(loglog(x)).
Local Sherman's Algorithm for Multi-commodity Flow [pdf]
Jason Li, Thatchaphol Saranurak
2025
Deterministic k-Vertex Connectivity in k^2 Max-flows [pdf]
Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2023
Deterministic Weighted Expander Decomposition in Almost-linear Time [pdf]
Jason Li and Thatchaphol Saranurak
2021
Summary: Generalize our fast deterministic expander decomposition to work on weighted graphs with general demand.
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
Fast Incremental Algorithms via Local Sparsifiers [pdf]
Gramoz Goranci, Monika Henzinger and Thatchaphol Saranurak
2018
Summary: A generic transformation from vertex sparsifiers to dynamic algorithms (merged into this paper).
Binary search trees and rectangulations [pdf]
László Kozma and Thatchaphol Saranurak
2016
Summary: Connections in this paper lead to our discovery of the Smooth heaps [9].
The landscape of bounds for binary search trees [pdf]
Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, László Kozma and Thatchaphol Saranurak
2016
Summary: A comprehensive list of connections between instance-specific bounds for binary search trees.
Subtraction makes computing integers faster [pdf]
Gorav Jindal and Thatchaphol Saranurak
2012
Improving stretch bound on the Patrascu-Roditty Distance Oracle [pdf]
Jittat Fackcharoenphol and Thatchaphol Saranurak
2010
Amir Abboud, Deeksha Adil, Aditya Anand, Amos Beimel, Aaron Bernstein, Sayan Bhattacharya, Joakim Blikstad, Jan van den Brand, Niv Buchbinder, Matija Bucic, Ruoxu Cen, Parinya Chalermsook, Yi-Jun Chang, Daoyuan Chen, Li Chen, Julia Chuzhoy, Mohit Daga, Jittat Fackcharoenphol, Nick Fischer, Henry Fleischmann, Sebastian Forster, Yu Gao, Gramoz Goranci, Mayank Goswami, Maximilian Probst Gutenberg, Bernhard Haeupler, Monika Henzinger, Zhongtian He, D Ellis Hershkowitz, Gary Hoppenworth, Chien-Chung Huang, Shang-En Huang, Zhiyi Huang, Yonggang Jiang, Gorav Jindal, Haim Kaplan, Peter Kiss, László Kozma, Robert Krauthgamer, Rasmus Kyng, Euiwoong Lee, Yin-Tat Lee, Roie Levin, George Li, Jason Li, Yang Liu, Yaowei Long, Yishay Mansour, Kurt Mehlhorn, Simon Meierhans, Chaitanya Nalam, Danupon Nanongkai, Kobbi Nissim, Debmalya Panigrahi, Richard Peng, Seth Pettie, Harald Räcke, Antti Röyskö, Leon Schiller, Aaron Sidford, Zhao Song, Uri Stemmer, Pattara Sukprasert, He Sun, Zihan Tan, Mikkel Thorup, Ohad Trabelsi, Ta-Wei Tu, Benyu Wang, Di Wang, Shengzhe Wang, Yunfan Wang, Christian Wulff-Nilsen, Longhui Yin, Sorrachai Yingchareonthawornchai, Weixuan Yuan, Wuwei Yuan, Hengjie Zhang