research
∙
04/18/2023
A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in un...
share
research
∙
11/19/2022
A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems
Expander graphs play a central role in graph theory and algorithms. With...
research
∙
11/10/2022
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems
We propose a new conjecture on hardness of low-degree 2-CSP's, and show ...
research
∙
02/14/2022
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
We consider the classical Minimum Crossing Number problem: given an n-ve...
research
∙
09/12/2021
Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time
We study the decremental All-Pairs Shortest Paths (APSP) problem in undi...
research
∙
11/12/2020
Towards Better Approximation of Graph Crossing Number
Graph Crossing Number is a fundamental problem with various applications...
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...
research
∙
06/12/2020
On Packing Low-Diameter Spanning Trees
Edge connectivity of a graph is one of the most fundamental graph-theore...
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...
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,...
research
∙
05/27/2019
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
We study the vertex-decremental Single-Source Shortest Paths (SSSP) prob...
research
∙
01/27/2019
Large Minors in Expanders
In this paper we study expander graphs and their minors. Specifically, w...
research
∙
01/23/2019
Towards Tight(er) Bounds for the Excluded Grid Theorem
We study the Excluded Grid Theorem, a fundamental structural result in g...
research
∙
05/25/2018
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary
We study the classical Node-Disjoint Paths (NDP) problem: given an undir...
research
∙
11/06/2017
