Thatchaphol Saranurak

According to our database, Thatchaphol Saranurak authored at least 75 papers between 2012 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Approximating Small Sparse Cuts.

Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak

CoRR, 2024

Dynamic Deterministic Constant-Approximate Distance Oracles with n^ε Worst-Case Update Time.

Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak

CoRR, 2024

Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method.

Deeksha Adil, Thatchaphol Saranurak

CoRR, 2024

Cactus Representation of Minimum Cuts: Derandomize and Speed up.

Zhongtian He, Shang-En Huang, Thatchaphol Saranurak

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

Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts.

Zhongtian He, Shang-En Huang, Thatchaphol Saranurak

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

2023

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

Jason Li, Debmalya Panigrahi, Laura Sanità, Thatchaphol Saranurak

Dagstuhl Reports, 2023

Deterministic k-Vertex Connectivity in k² Max-flows.

Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

CoRR, 2023

Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction.

Chaitanya Nalam, Thatchaphol Saranurak

CoRR, 2023

Tight Conditional Lower Bounds for Vertex Connectivity Problems.

Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast.

Bernhard Haeupler, D. Ellis Hershkowitz, Thatchaphol Saranurak

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Sublinear Algorithms for (1.5+ε)-Approximate Matching.

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Maximal <i>k</i>-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction.

Chaitanya Nalam, Thatchaphol Saranurak

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

Fully Dynamic Exact Edge Connectivity in Sublinear Time.

Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen

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

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc

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

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates.

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

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

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

Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak

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

Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time.

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

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

Chasing Positive Bodies.

Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak

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

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

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

Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k.

Thatchaphol Saranurak, Wuwei Yuan

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

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

Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak

CoRR, 2022

Optimal vertex connectivity oracles.

Seth Pettie, Thatchaphol Saranurak, Longhui Yin

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

Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds.

Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, Uri Stemmer

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

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver.

Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.

Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Deterministic Small Vertex Connectivity in Almost Linear Time.

Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

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

Near-Optimal Deterministic Vertex-Failure Connectivity Oracles.

Yaowei Long, Thatchaphol Saranurak

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

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

Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi

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

Vertex Sparsifiers for Hyperedge Connectivity.

Han Jiang, Shang-En Huang, Thatchaphol Saranurak, Tian Zhang

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary.

Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Near-optimal Distributed Triangle Enumeration via Expander Decompositions.

Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, Hengjie Zhang

J. ACM, 2021

Gomory-Hu Tree in Subcubic Time.

Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi

CoRR, 2021

Fast Algorithms for Hop-Constrained Flows and Moving Cuts.

Bernhard Haeupler, D. Ellis Hershkowitz, Thatchaphol Saranurak

CoRR, 2021

Deterministic Weighted Expander Decomposition in Almost-linear Time.

Jason Li, Thatchaphol Saranurak

CoRR, 2021

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

Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak

CoRR, 2021

Vertex connectivity in poly-logarithmic max-flows.

Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

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

Minimum cost flows, MDPs, and ℓ₁-regression in nearly linear time for dense instances.

Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang

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

A Simple Deterministic Algorithm for Edge Connectivity.

Thatchaphol Saranurak

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms.

Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan

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

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition.

Julia Chuzhoy, Thatchaphol Saranurak

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

Minimum Cuts in Directed Graphs via Partial Sparsification.

Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud

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

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.

Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

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

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

Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak

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

2020

Smooth Heaps and a Dual View of Self-Adjusting Data Structures.

László Kozma, Thatchaphol Saranurak

SIAM J. Comput., 2020

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms.

Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

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

Coarse-Grained Complexity for Dynamic Algorithms.

Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak

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

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

Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak

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

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.

Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, Thatchaphol Saranurak

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

Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization.

Yi-Jun Chang, Thatchaphol Saranurak

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

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.

Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang

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

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.

Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

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

Pinning down the Strong Wilber 1 Bound for Binary Search Trees.

Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak

Proceedings of the Approximation, 2020

2019

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

Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

CoRR, 2019

Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries.

Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

CoRR, 2019

Breaking quadratic time for small vertex connectivity and an approximation scheme.

Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

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

Distributed edge connectivity in sublinear time.

Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak

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

Expander Decomposition and Pruning: Faster, Stronger, and Simpler.

Thatchaphol Saranurak, Di Wang

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

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration.

Yi-Jun Chang, Thatchaphol Saranurak

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

Sensitive Distance and Reachability Oracles for Large Batch Updates.

Jan van den Brand, Thatchaphol Saranurak

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

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds.

Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak

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

2018

Dynamic algorithms: new worst-case and instance-optimal bounds via new connections.

Thatchaphol Saranurak

PhD thesis, 2018

Multi-Finger Binary Search Trees.

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^{1/2 - ε})-time.

Danupon Nanongkai, Thatchaphol Saranurak

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time.

Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^5/4) Rounds.

Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time.

Danupon Nanongkai, Thatchaphol Saranurak

CoRR, 2016

The landscape of bounds for binary search trees.

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

CoRR, 2016

Binary search trees and rectangulations.

László Kozma, Thatchaphol Saranurak

CoRR, 2016

2015

A Global Geometric View of Splaying.

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

CoRR, 2015

Greedy Is an Almost Optimal Deque.

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Pattern-Avoiding Access in Binary Search Trees.

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Self-Adjusting Binary Search Trees: What Makes Them Tick?

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

Proceedings of the Algorithms - ESA 2015, 2015

2013

Finding the colors of the secret in Mastermind.

Thatchaphol Saranurak

Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2013

2012

Subtraction makes computing integers faster

Thatchaphol Saranurak, Gorav Jindal

CoRR, 2012