12 citations · 20 across the 13 of their papers we have counts for
5 papers · 1 filter
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…
Query Complexity of the Metric Steiner Tree Problem
Yu Chen, Sanjeev Khanna, Zihan Tan
We study the query complexity of the metric Steiner Tree problem, where we are given an metric on a set of vertices along with a set of termina…
Near-Linear -Emulators for Planar Graphs
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph (with edge weights) and a subset of terminal vertices, t…
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
Yu Chen, Sanjeev Khanna, Zihan Tan
We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP…
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…