Thatchaphol Saranurak

David Wajc

J. ACM, October, 2024

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies.

[BibT_eX]

[DOI]

Seth Pettie

CoRR, 2024

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries.

[BibT_eX]

[DOI]

Aditya Anand

Yunfan Wang

CoRR, 2024

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal.

[BibT_eX]

[DOI]

Daoyuan Chen

Simon Meierhans

CoRR, 2024

Unbreakable Decomposition in Close-to-Linear Time.

[BibT_eX]

[DOI]

CoRR, 2024

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

[BibT_eX]

[DOI]

Deeksha Adil

CoRR, 2024

Low-Step Multi-commodity Flow Emulators.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Approximating Small Sparse Cuts.

[BibT_eX]

[DOI]

Aditya Anand

Euiwoong Lee

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Cactus Representation of Minimum Cuts: Derandomize and Speed up.

[BibT_eX]

[DOI]

Zhongtian He

Shang-En Huang

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

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

[BibT_eX]

[DOI]

Zhongtian He

Shang-En Huang

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

Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time.

[BibT_eX]

[DOI]

Kevin Hua

Daniel Li

Jaewoo Park

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

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

[BibT_eX]

[DOI]

Bernhard Haeupler

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Maximum Flow by Augmenting Paths in n2+o(1) Time.

[BibT_eX]

[DOI]

Joakim Blikstad

Ta-Wei Tu

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Pinning Down the Strong Wilber-1 Bound for Binary Search Trees.

[BibT_eX]

[DOI]

Parinya Chalermsook

Julia Chuzhoy

Theory Comput., 2023

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

[BibT_eX]

[DOI]

Laura Sanità

Dagstuhl Reports, 2023

Deterministic k-Vertex Connectivity in k2 Max-flows.

[BibT_eX]

[DOI]

Chaitanya Nalam

CoRR, 2023

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

[BibT_eX]

[DOI]

Chaitanya Nalam

CoRR, 2023

Tight Conditional Lower Bounds for Vertex Connectivity Problems.

[BibT_eX]

[DOI]

Zhiyi Huang

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.

[BibT_eX]

[DOI]

Bernhard Haeupler

D. Ellis Hershkowitz

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Chaitanya Nalam

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

Fully Dynamic Exact Edge Connectivity in Sublinear Time.

[BibT_eX]

[DOI]

Gramoz Goranci

Monika Henzinger

Mikkel Thorup

Christian Wulff-Nilsen

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

Chasing Positive Bodies.

[BibT_eX]

[DOI]

Niv Buchbinder

Roie Levin

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.

[BibT_eX]

[DOI]

Amir Abboud

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

CoRR, 2022

Optimal vertex connectivity oracles.

[BibT_eX]

[DOI]

Seth Pettie

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Parinya Chalermsook

Chien-Chung Huang

Pattara Sukprasert

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

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.

[BibT_eX]

[DOI]

Aaron Sidford

He Sun

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

Deterministic Small Vertex Connectivity in Almost Linear Time.

[BibT_eX]

[DOI]

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

Near-Optimal Deterministic Vertex-Failure Connectivity Oracles.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Ohad Trabelsi

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

Vertex Sparsifiers for Hyperedge Connectivity.

[BibT_eX]

[DOI]

Han Jiang

Shang-En Huang

Tian Zhang

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

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

[BibT_eX]

[DOI]

Pattara Sukprasert

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

2021

Near-optimal Distributed Triangle Enumeration via Expander Decompositions.

[BibT_eX]

[DOI]

Yi-Jun Chang

Seth Pettie

Hengjie Zhang

J. ACM, 2021

Gomory-Hu Tree in Subcubic Time.

[BibT_eX]

[DOI]

Ohad Trabelsi

CoRR, 2021

Fast Algorithms for Hop-Constrained Flows and Moving Cuts.

[BibT_eX]

[DOI]

Bernhard Haeupler

D. Ellis Hershkowitz

CoRR, 2021

Deterministic Weighted Expander Decomposition in Almost-linear Time.

[BibT_eX]

[DOI]

CoRR, 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

Vertex connectivity in poly-logarithmic max-flows.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Yin Tat Lee

Yang P. Liu

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.

[BibT_eX]

[DOI]

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

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms.

[BibT_eX]

[DOI]

Gramoz Goranci

Harald Räcke

Zihan Tan

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

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition.

[BibT_eX]

[DOI]

Julia Chuzhoy

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

Minimum Cuts in Directed Graphs via Partial Sparsification.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

László Kozma

SIAM J. Comput., 2020

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

[BibT_eX]

[DOI]

Sebastian Forster

Liu Yang

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

Coarse-Grained Complexity for Dynamic Algorithms.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Yi-Jun Chang

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

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2019

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

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

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

Distributed edge connectivity in sublinear time.

[BibT_eX]

[DOI]

Mohit Daga

Monika Henzinger

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

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

[BibT_eX]

[DOI]

Di Wang

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

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration.

[BibT_eX]

[DOI]

Yi-Jun Chang

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

Sensitive Distance and Reachability Oracles for Large Batch Updates.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

PhD thesis, 2018

Multi-Finger Binary Search Trees.

[BibT_eX]

[DOI]

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(n1/2 - ε)-time.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Christian Wulff-Nilsen

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

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

[BibT_eX]

[DOI]

Chien-Chung Huang

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.

[BibT_eX]

[DOI]

CoRR, 2016

The landscape of bounds for binary search trees.

[BibT_eX]

[DOI]

CoRR, 2016

Binary search trees and rectangulations.

[BibT_eX]

[DOI]

László Kozma

CoRR, 2016

2015

A Global Geometric View of Splaying.

[BibT_eX]

[DOI]

CoRR, 2015

Greedy Is an Almost Optimal Deque.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Monika Henzinger

Sebastian Krinninger

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

Pattern-Avoiding Access in Binary Search Trees.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

2013

Finding the colors of the secret in Mastermind.

[BibT_eX]

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

2012

Subtraction makes computing integers faster

[BibT_eX]

[DOI]