Valency Hub
alphaFeedback
TS

Thatchaphol Saranurak

0000-0001-8386-7168
cs.DSmath.COcs.DCcs.CCmath.OCcs.CGcs.DM

On Valency

published · living versions
W_uqhr6nx7·v1 · currentpublished
Polynomial Lower Bounds for Steiner Shortcuts via Test Functions
with Aaron Bernstein, Henry Fleischmann, Bernhard Haeupler, Gary Hoppenworth
1 version
W_6g6f433w·v1published
Local Important Separators with Applications to Unbreakable Decomposition and Multicut
W_g9z927n8·v1published
Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

Preprints & journals

98 papers in the corpus · 2012–2026
Dynamic Load Balancing under Restricting Updates2610.23768v1 · Aaron Bernstein, Sayan Bhattacharya, Peter Kiss et al.2026 · 0 citationsarXiv
Directed Global Minimum Cut in Almost-Linear Time2610.10898v2 · Henry Fleischmann, Jason Li, Thatchaphol Saranurak et al.2026 · 0 citationsarXiv
Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size2609.09031v2 · Yaowei Long, Seth Pettie, Thatchaphol Saranurak2026 · 0 citationsarXiv
Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition2609.02388v1 · Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak et al.2026 · 0 citationsarXiv
Incremental Directed Minimum Cut by Dynamizing Gabow's Algorithm2608.16382v1 · Thatchaphol Saranurak, Kaiyang Xie, Zhaienhe Zhou2026 · 0 citationsarXiv
Minimum Degree Spanning Tree: (1+ϵ,1)(1+\epsilon,1)-Approximation in Near-Linear Time2607.11413v1 · Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak et al.2026 · 0 citationsarXiv
Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition2605.07168v1 · Xizhe Li, Yaowei Long, David Pidugu et al.2026 · 0 citationsarXiv
Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth2605.03892v1 · Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg et al.2026 · 0 citationsarXiv
DAG Projections: Reducing Distance and Flow Problems to DAGs2604.04752v1 · Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak2026 · 0 citationsarXiv
A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures2604.01829v1 · Bernhard Haeupler, Yaowei Long, Antti Roeyskoe et al.2026 · 0 citationsarXiv
Expander Decomposition with Almost Optimal Overhead2602.15015v2 · Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak2026 · 0 citationsarXiv
Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies2512.05300v2 · Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak et al.2025 · 0 citationsarXiv
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers2511.08551v1 · Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak2025 · 0 citationsarXiv
Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching2511.02214v1 · Matija Buci'c, Zhongtian He, Shang-En Huang et al.2025 · 0 citationsarXiv
Reviving Thorup's Shortcut Conjecture2510.24954v2 · Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg et al.2025 · 0 citationsarXiv
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems2510.20341v1 · Aaron Bernstein, Sayan Bhattacharya, Nick Fischer et al.2025 · 0 citationsarXiv
Parallel (1+ϵ)(1+\epsilon)-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work2510.20456v1 · Bernhard Haeupler, Yonggang Jiang, Yaowei Long et al.2025 · 0 citationsarXiv
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs2510.17182v1 · Aaron Bernstein, Joakim Blikstad, Jason Li et al.2025 · 2 citationsarXiv
Near-Optimal Fault-Tolerant Strong Connectivity Preservers2510.02562v1 · Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang2025 · 1 citationarXiv
Reducing Shortcut and Hopset Constructions to Shallow Graphs2508.20302v1 · Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak2025 · 0 citationsarXiv
Deterministic Almost-Linear-Time Gomory-Hu Trees2507.20354v1 · Amir Abboud, Rasmus Kyng, Jason Li et al.2025 · 1 citationarXiv
Deterministic Dynamic Maximal Matching in Sublinear Update Time2504.20780v2 · Aaron Bernstein, Sayan Bhattacharya, Peter Kiss et al.2025 · 1 citationarXiv
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs2504.20027v1 · Aditya Anand, Euiwoong Lee, Jason Li et al.2025 · 0 citationsarXiv
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time2504.00544v1 · Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak2025 · 0 citationsarXiv
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts2503.23217v1 · Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak et al.2025 · 0 citationsarXiv
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness2503.20985v1 · Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak et al.2025 · 1 citationarXiv
Local Sherman's Algorithm for Multi-commodity Flow2501.10632v2 · Jason Li, Thatchaphol Saranurak2025 · 0 citationsarXiv
Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries2410.18704v1 · Aditya Anand, Thatchaphol Saranurak, Yunfan Wang2024 · 0 citationsarXiv
Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies2410.18885v1 · Yaowei Long, Seth Pettie, Thatchaphol Saranurak2024 · 3 citationsarXiv
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal2410.13451v2 · Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg et al.2024 · 4 citationsarXiv
Unbreakable Decomposition in Close-to-Linear Time2408.09368v1 · Aditya Anand, Euiwoong Lee, Jason Li et al.2024 · 1 citationarXiv
Low-Step Multi-Commodity Flow Emulators2406.14384v1 · Bernhard Haeupler, D Ellis Hershkowitz, Jason Li et al.2024 · 7 citationsarXiv
Maximum Flow by Augmenting Paths in n2+o(1)n^{2+o(1)} Time2406.03648v2 · Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak et al.2024 · 4 citationsarXiv
Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time2405.03801v2 · Kevin Hua, Daniel Li, Jaewoo Park et al.2024 · 0 citationsarXiv
Approximating Small Sparse Cuts2403.08983v1 · Aditya Anand, Euiwoong Lee, Jason Li et al.2024 · 3 citationsarXiv
Dynamic Deterministic Constant-Approximate Distance Oracles with nϵn^{\epsilon} Worst-Case Update Time2402.18541v2 · Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak2024 · 4 citationsarXiv
Decremental (1+ϵ)(1+\epsilon)-Approximate Maximum Eigenvector: Dynamic Power Method2402.17929v2 · Deeksha Adil, Thatchaphol Saranurak2024 · 0 citationsarXiv
Cactus Representation of Minimum Cuts: Derandomize and Speed up2401.10856v1 · Zhongtian He, Shang-En Huang, Thatchaphol Saranurak2024 · 0 citationsarXiv
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts2311.10706v1 · Zhongtian He, Shang-En Huang, Thatchaphol Saranurak2023 · 1 citationarXiv
Deterministic kk-Vertex Connectivity in k2k^2 Max-flows2308.04695v1 · Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai2023 · 2 citationsarXiv
Maximal kk-Edge-Connected Subgraphs in Almost-Linear Time for Small kk2307.00147v1 · Thatchaphol Saranurak, Wuwei Yuan2023 · 0 citationsarXiv
Chasing Positive Bodies2304.01889v2 · Sayan Bhattacharya, Niv Buchbinder, Roie Levin et al.2023 · 6 citationsarXiv
Fully Dynamic Exact Edge Connectivity in Sublinear Time2302.05951v2 · Gramoz Goranci, Monika Henzinger, Danupon Nanongkai et al.2023 · 3 citationsarXiv
Dynamic (1+ϵ)(1+\epsilon)-Approximate Matching Size in Truly Sublinear Update Time2302.05030v3 · Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak2023 · 9 citationsarXiv
Maximal kk-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction2302.02290v1 · Chaitanya Nalam, Thatchaphol Saranurak2023 · 0 citationsarXiv
Sublinear Algorithms for (1.5+ϵ)(1.5+\epsilon)-Approximate Matching2212.00189v2 · Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak2022 · 0 citationsarXiv
Tight Conditional Lower Bounds for Vertex Connectivity Problems2212.00359v2 · Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak et al.2022 · 5 citationsarXiv
Deterministic Small Vertex Connectivity in Almost Linear Time2210.13739v1 · Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai2022 · 7 citationsarXiv
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time2207.07438v3 · Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak et al.2022 · 11 citationsarXiv
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates2207.07519v1 · Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak2022 · 10 citationsarXiv
Career total: 145 works. 98 are in this corpus.Showing the 50 most recent.

Profile built from the corpus for this byline.

Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.