32 citations · 59 across the 26 of their papers we have counts for
5 papers · 1 filter
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak
The dynamic optimality conjecture, postulating the existence of an -competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems i…
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Julia Chuzhoy, Yu Gao, Jason Li +3
We consider the classical Minimum Balanced Cut problem: given a graph , compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number…
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
Julia Chuzhoy, Sanjeev Khanna
We study the vertex-decremental Single-Source Shortest Paths (SSSP) problem: given an undirected graph with lengths on its edges and a source vertex ,…
Large Minors in Expanders
Julia Chuzhoy, Rachit Nimavat
In this paper we study expander graphs and their minors. Specifically, we attempt to answer the following question: what is the largest function , such that every -ver…
Towards Tight(er) Bounds for the Excluded Grid Theorem
Julia Chuzhoy, Zihan Tan
We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem sta…