Thatchaphol Saranurak

research

∙ 08/09/2023

Deterministic k-Vertex Connectivity in k^2 Max-flows

An n-vertex m-edge graph is k-vertex connected if it cannot be disconnec...

0 Chaitanya Nalam, et al. ∙

research

∙ 06/30/2023

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

We give the first almost-linear time algorithm for computing the maximal...

0 Thatchaphol Saranurak, et al. ∙

research

∙ 04/04/2023

Chasing Positive Bodies

We study the problem of chasing positive bodies in ℓ_1: given a sequence...

0 Sayan Bhattacharya, et al. ∙

research

∙ 02/12/2023

Fully Dynamic Exact Edge Connectivity in Sublinear Time

Given a simple n-vertex, m-edge graph G undergoing edge insertions and d...

0 Gramoz Goranci, et al. ∙

research

∙ 02/10/2023

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

We show a fully dynamic algorithm for maintaining (1+ϵ)-approximate size...

0 Sayan Bhattacharya, et al. ∙

research

∙ 02/05/2023

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

The maximal k-edge-connected subgraphs problem is a classical graph clus...

0 Chaitanya Nalam, et al. ∙

research

∙ 12/01/2022

Tight Conditional Lower Bounds for Vertex Connectivity Problems

We study the fine-grained complexity of graph connectivity problems in u...

0 Zhiyi Huang, et al. ∙

research

∙ 12/01/2022

Sublinear Algorithms for (1.5+ε)-Approximate Matching

We study sublinear time algorithms for estimating the size of maximum ma...

0 Sayan Bhattacharya, et al. ∙

research

∙ 10/25/2022

Deterministic Small Vertex Connectivity in Almost Linear Time

In the vertex connectivity problem, given an undirected n-vertex m-edge ...

0 Thatchaphol Saranurak, et al. ∙

research

∙ 07/15/2022

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates

In the dynamic linear program (LP) problem, we are given an LP undergoin...

0 Sayan Bhattacharya, et al. ∙

research

∙ 07/15/2022

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

We present dynamic algorithms with polylogarithmic update time for estim...

0 Sayan Bhattacharya, et al. ∙

research

∙ 07/11/2022

Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary

Designing dynamic algorithms against an adaptive adversary whose perform...

0 Sayan Bhattacharya, et al. ∙

research

∙ 07/08/2022

Vertex Sparsifiers for Hyperedge Connectivity

Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a no...

0 Han Jiang, et al. ∙

research

∙ 05/30/2022

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

In the k-edge-connected spanning subgraph (kECSS) problem, our goal is t...

0 Parinya Chalermsook, et al. ∙

research

∙ 05/08/2022

Near-Optimal Deterministic Vertex-Failure Connectivity Oracles

We revisit the vertex-failure connectivity oracle problem. This is one o...

0 Yaowei Long, et al. ∙

research

∙ 03/01/2022

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

In this paper, we introduce a robust notion of (1+ϵ)-approximate (s, t)-...

0 Jason Li, et al. ∙

research

∙ 01/02/2022

Optimal Vertex Connectivity Oracles

A k-vertex connectivity oracle for undirected G is a data structure that...

0 Seth Pettie, et al. ∙

research

∙ 11/17/2021

Minimum Cuts in Directed Graphs via Partial Sparsification

We give an algorithm to find a minimum cut in an edge-weighted directed ...

0 Ruoxu Cen, et al. ∙

research

∙ 11/09/2021

Gomory-Hu Tree in Subcubic Time

In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...

0 Amir Abboud, et al. ∙

research

∙ 11/07/2021

Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds

A dynamic algorithm against an adaptive adversary is required to be corr...

0 Amos Beimel, et al. ∙

research

∙ 11/02/2021

Fast Algorithms for Hop-Constrained Flows and Moving Cuts

Hop-constrained flows and their duals, moving cuts, are two fundamental ...

0 Bernhard Haeupler, et al. ∙

research

∙ 06/04/2021

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

We give an n^2+o(1)-time algorithm for finding s-t min-cuts for all pair...

0 Jason Li, et al. ∙

research

∙ 06/03/2021

Deterministic Weighted Expander Decomposition in Almost-linear Time

In this note, we study the expander decomposition problem in a more gene...

0 Jason Li, et al. ∙

research

∙ 04/16/2021

Minimum Cuts in Directed Graphs via √(n) Max-Flows

We give an algorithm to find a mincut in an n-vertex, m-edge weighted di...

0 Ruoxu Cen, et al. ∙

research

∙ 03/31/2021

Vertex Connectivity in Poly-logarithmic Max-flows

The vertex connectivity of an m-edge n-vertex undirected graph is the sm...

0 Jason Li, et al. ∙

research

∙ 01/18/2021

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

In the decremental single-source shortest paths problem, the goal is to ...

0 Aaron Bernstein, et al. ∙

research

∙ 01/14/2021

Minimum Cost Flows, MDPs, and ℓ_1-Regression in Nearly Linear Time for Dense Instances

In this paper we provide new randomized algorithms with improved runtime...

0 Jan van den Brand, et al. ∙

research

∙ 09/17/2020

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition

In the decremental single-source shortest paths (SSSP) problem, the inpu...

0 Julia Chuzhoy, et al. ∙

research

∙ 09/05/2020

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

Let G = (V,E,w) be a weighted, digraph subject to a sequence of adversar...

0 Aaron Bernstein, et al. ∙

research

∙ 09/03/2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...

0 Jan van den Brand, et al. ∙

research

∙ 08/19/2020

A Simple Deterministic Algorithm for Edge Connectivity

We show a deterministic algorithm for computing edge connectivity of a s...

0 Thatchaphol Saranurak, et al. ∙

research

∙ 07/29/2020

Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization

There is a recent exciting line of work in distributed graph algorithms ...

0 Yi-Jun Chang, et al. ∙

research

∙ 05/05/2020

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

We introduce a notion for hierarchical graph clustering which we call th...

0 Gramoz Goranci, et al. ∙

research

∙ 05/05/2020

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

We present a general framework of designing efficient dynamic approximat...

0 Li Chen, et al. ∙

research

∙ 04/17/2020

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Designing dynamic graph algorithms against an adaptive adversary is a ma...

0 Aaron Bernstein, et al. ∙

research

∙ 01/02/2020

Coarse-Grained Complexity for Dynamic Algorithms

To date, the only way to argue polynomial lower bounds for dynamic algor...

0 Sayan Bhattacharya, et al. ∙

research

∙ 12/05/2019

Pinning Down the Strong Wilber 1 Bound for Binary Search Trees

The famous dynamic optimality conjecture of Sleator and Tarjan from 1985...

0 Parinya Chalermsook, et al. ∙

research

∙ 10/31/2019

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

Consider the following "local" cut-detection problem in a directed graph...

0 Sebastian Forster, et al. ∙

research

∙ 10/17/2019

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

We consider the classical Minimum Balanced Cut problem: given a graph G,...

0 Julia Chuzhoy, et al. ∙

research

∙ 10/17/2019

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

We study deterministic algorithms for computing graph cuts, with focus o...

0 Yu Gao, et al. ∙

research

∙ 07/18/2019

Sensitive Distance and Reachability Oracles for Large Batch Updates

In the sensitive distance oracle problem, there are three phases. We fir...

0 Jan van den Brand, et al. ∙

research

∙ 05/14/2019

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

We present a new, simple, algorithm for the local vertex connectivity pr...

0 Danupon Nanongkai, et al. ∙

research

∙ 05/13/2019

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds

The dynamic matrix inverse problem is to maintain the inverse of a matri...

0 Jan van den Brand, et al. ∙

research

∙ 04/17/2019

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration

An (ϵ,ϕ)-expander decomposition of a graph G=(V,E) is a clustering of th...

0 Yi-Jun Chang, et al. ∙

research

∙ 04/09/2019

Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme

Vertex connectivity a classic extensively-studied problem. Given an inte...

0 Danupon Nanongkai, et al. ∙

research

∙ 04/08/2019

Distributed Edge Connectivity in Sublinear Time

We present the first sublinear-time algorithm for a distributed message-...

0 Mohit Daga, et al. ∙

research

∙ 12/21/2018

Expander Decomposition and Pruning: Faster, Stronger, and Simpler

We study the problem of graph clustering where the goal is to partition ...

0 Thatchaphol Saranurak, et al. ∙

research

∙ 09/05/2018

Multi-finger binary search trees

We study multi-finger binary search trees (BSTs), a far-reaching extensi...

0 Parinya Chalermsook, et al. ∙

research

∙ 02/15/2018

Smooth heaps and a dual view of self-adjusting data structures

We present a new connection between self-adjusting binary search trees (...

0 László Kozma, et al. ∙

Thatchaphol Saranurak

Featured Co-authors