Publications

[DBLP] [Google Scholar]

Unless stated otherwise, author names are in alphabetical order. 

Recent Manuscripts

Deterministic k-Vertex Connectivity in k^2 Max-flows [pdf]
Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method [pdf]
Deeksha Adil, Thatchaphol Saranurak

Dynamic Deterministic Constant-Approximate Distance Oracles with n^ε Worst-Case Update Time [pdf]
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak

Conference Papers

2024

58. Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time [pdf]
Kevin Hua, Daniel Li, Jaewoo Park and Thatchaphol Saranurak
ICALP 2024

57. Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Röyskö, Thatchaphol Saranurak
STOC 2024

56. Approximating Small Sparse Cuts [pdf]
Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak
STOC 2024

55. Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts [pdf]
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
SODA 2024

54. Cactus Representation of Minimum Cuts: Derandomize and Speed up  [pdf]
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
SODA 2024

2023

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
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

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
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. 

2022

41. Deterministic Small Vertex Connectivity in Almost Linear Time [pdf]  [video by SY]
Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
FOCS 2022
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
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.
FOCS 2022

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
Summary: Break the 60-year-old n^3-time barrier for Gomory-Hu trees (all-pairs max flows) to n^2. 
FOCS 2022
Invited to SICOMP Special Issue 

38. Vertex Sparsifiers for Hyperedge Connectivity [pdf]
Han Jiang, Shang-En Huang, Thatchaphol Saranurak, Tian Zhang
Summary: Generalize the cool results of these papers to hypergraphs. 
ESA 2022

37. Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary [pdf]
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert.
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.
ESA 2022

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
Summary: Solve LP for the k-ECSS problem in near-linear time.
ICALP 2022 

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
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.
ICALP 2022

34. Optimal Vertex Connectivity Oracles [pdf] [video]
Seth Pettie, Thatchaphol Saranurak, Longhui Yin
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.
STOC 2022

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
Summary: Connect dynamic algorithms to differential privacy, cryptography, and adaptive data analysis.
STOC 2022

2021

32. A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs  [pdf]
Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
Summary: All-pairs min-cuts in n^{2+o(1)} time (which is tight with the output size).
FOCS 2021

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

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
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).

2020

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.

2019

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.

2018

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.

2017

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).

2015 and Earlier

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.

Journal Papers

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 

PhD Thesis

Dynamic algorithms: new worst-case and instance-optimal bounds via new connections [link]
supervised by Danupon Nanongkai in KTH

Master Thesis

PosSLP and The Monotone Complexity of Computing Integers [pdf]
supervised by Markus Bläser in 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)).

Old Manuscripts

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