3 citations · 4 across the 4 of their papers we have counts for
6 papers
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest -Subgraph and Other Problems
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg +1
We propose a new conjecture on hardness of low-degree -CSP's, and show that new hardness of approximation results for Densest -Subgraph and several other problems, including…
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Julia Chuzhoy, Zihan Tan
We consider the classical Minimum Crossing Number problem: given an -vertex graph , compute a drawing of in the plane, while minimizing the number of crossings between th…
Towards Better Approximation of Graph Crossing Number
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph in the plane so as to minimize the number of cross…
On Packing Low-Diameter Spanning Trees
Julia Chuzhoy, Merav Parter, Zihan Tan
Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every …
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak +1
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with …
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…