Publications

We consider the sparsification of sums \(F : \mathbb{R}^n \to \mathbb{R}_+\) where \(F(x) = f_1(\langle a_1,x\rangle) + \cdots + f_m(\langle a_m,x\rangle)\) for vectors $a_1,\ldots,a_m \in \mathbb{R}^n$ and functions $f_1,\ldots,f_m : \mathbb{R} \to \mathbb{R}_+$. We show that $(1+\varepsilon)$-approximate sparsifiers of $F$ with support size $\frac{n}{\varepsilon^2} (\log \frac{n}{\varepsilon})^{O(1)}$ exist whenever the functions $f_1,\ldots,f_m$ are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each $f_i$ can be evaluated efficiently.

Our results generalize the classic case of $\ell_p$ sparsification, where $f_i(z) = |z|^p$, for $p \in (0, 2]$, and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., $f_i(z) = \min{|z|^p, |z|^2}$ for $0 < p \leq 2$. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including $\ell_p$ regression for $p \in (1, 2]$ to high accuracy, via solving $(\log n)^{O(1)}$ sparse regression instances with $m \le n(\log n)^{O(1)}$, plus runtime proportional to the number of nonzero entries in the vectors $a_1, \dots, a_m$.

For any norms $N_1,\ldots,N_m$ on $\mathbb{R}^n$ and $N(x) := N_1(x)+\cdots+N_m(x)$, we show there is a sparsified norm $\tilde{N}(x) = w_1 N_1(x) + \cdots + w_m N_m(x)$ such that $|N(x) - \tilde{N}(x)| \leq \epsilon N(x)$ for all $x \in \mathbb{R}^n$, where $w_1,\ldots,w_m$ are non-negative weights, of which only $O(\epsilon^{-2} n \log(n/\epsilon) (\log n)^{2.5} )$ are non-zero.

Additionally, we show that such weights can be found with high probability in time $O(m (\log n)^{O(1)} + \mathrm{poly}(n)) T$, where $T$ is the time required to evaluate a norm $N_i(x)$, assuming that $N(x)$ is $\mathrm{poly}(n)$-equivalent to the Euclidean norm. This immediately yields analogous statements for sparsifying sums of symmetric submodular functions. More generally, we show how to sparsify sums of $p$th powers of norms when the sum is $p$-uniformly smooth.

In a hypergraph on $n$ vertices where $D$ is the maximum size of a hyperedge, there is a weighted hypergraph spectral $\varepsilon$-sparsifier with at most $O(\varepsilon^{-2} \log(D) \cdot n \log n)$ hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve $O(\varepsilon^{-4} n (\log n)^3)$, as well as the bound $O(\varepsilon^{-2} D^3 n \log n)$ obtained by Bansal, Svensson, and Trevisan (2019).

We present an \(O((\log n)^2)\)-competitive algorithm for metrical task systems (MTS) on any \(n\)-point metric space that is also \(1\)-competitive for service costs. This matches the competitive ratio achieved by Bubeck, Cohen, Lee, and Lee (2019) and the refined competitive ratios obtained by Coester and Lee (2019). Those algorithms work by first randomly embedding the metric space into an ultrametric and then solving MTS there. In contrast, our algorithm is cast as regularized gradient descent where the regularizer is a multiscale metric entropy defined directly on the metric space. This answers an open question of Bubeck (Highlights of Algorithms, 2019).

Benjamini and Papasoglou (2011) showed that planar graphs with uniform polynomial volume growth admit $1$-dimensional annular separators: The vertices at graph distance $R$ from any vertex can be separated from those at distance $2R$ by removing at most $O(R)$ vertices. They asked whether geometric $d$-dimensional graphs with uniform polynomial volume growth similarly admit $(d − 1)$-dimensional annular separators when $d > 2$. We show that this fails in a strong sense: For any $d > 3$ and every $s > 1$, there is a collection of interior-disjoint spheres in $\mathbb{R}^d$ whose tangency graph $G$ has uniform polynomial growth, but such that all annular separators in $G$ have cardinality at least $R^s$.

There is a randomized online algorithm for metrical task systems (MTS) that is \(1\)-competitive for service costs and \(O(\log n)\)-competitive for movement costs. In general, these refined guarantees are optimal up to the implicit constant. While an \(O(\log n)\)-competitive algorithm for MTS on HST metrics was developed in BCLL19, that approach could only establish an \(O((\log n)^2)\)-competitive ratio when the service costs are required to be \(O(1)\)-competitive. Our algorithm is an instantiation of online mirror descent with the regularizer derived from a multiscale conditional entropy.

In fact, our algorithm satisfies a set of even more refined guarantees; we are able to exploit this property to combine it with known random embedding theorems and obtain, for any \(n\)-point metric space, a randomized algorithm that is \(1\)-competitive for service costs and \(O((\log n)^2)\)-competitive for movement costs.

We consider metrical task systems on tree metrics, and present an $O(\mathrm{depth} \times \log n)$-competitive randomized algorithm based on the mirror descent framework. For the special case of HSTs, we refine the standard approach based on combining unfair metrical task systems, yielding an $O(\log n)$-competitive algorithm. This is tight up to the implicit constant factor. Using known random embeddings of finite metric spaces into HSTs, this yields an $O((\log n)^2)$-competitive algorithm for general $n$-point spaces.

We establish new and improved bounds on the flow-cut gap in planar flow networks where the terminals lie on a small number of faces. The classical Okamura-Seymour theorem (1981) shows that when all terminals lie on a single face, the flow-cut gap is exactly 1. We show that if the terminals lie on $\gamma$ faces, the flow-cut gap is $O(\log \gamma)$. This is proved by embedding the terminal metric into a distribution over trees with distortion $O(\log \gamma)$, which is tight up to the implied constant factor.

We give a poly(log k)-competitive randomized algorithm for the k-server problem on general metric spaces. The best previous result independent of the underlying metric space is the 2k-1 competitive ratio established for the deterministic work function algorithm by Koutsoupias and Papadimitriou (1995).

Since deterministic algorithms can do no better than k on any metric space with at least k+1 points, this establishes that for every metric space on which the problem is non-trivial, randomized algorithms give an exponential improvement over deterministic algorithms. The approach employs our previous algorithm for the fractional k-server problem on HSTs.

We present an \(O((\log k)^2)\)-competitive randomized algorithm for the k-server problem on hierarchically separated trees (HSTs). This is the first o(k)-competitive randomized algorithm for which the competitive ratio is independent of the size of the underlying HST. Our algorithm is designed in the framework of online mirror descent where the mirror map is a multiscale entropy.

When combined with Bartal’s static HST embedding reduction, this leads to an \(O((\log k)^2 \log n)\)-competitive algorithm on any n-point metric space. We give a new dynamic HST embedding that yields an \(O((\log k)^3 \log \Delta)\)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most \(\Delta\).

A region intersection graph over a base graph \(G_0\) is a graph \(G\) whose vertices correspond to connected subsets of \(G_0\) with an edge between two vertices if the corresponding regions intersect. We show that if \(G_0\) excludes the complete graph \(K_h\) as a minor, then every region intersection graph over \(G_0\) with m edges has a balanced separator with \(O(\sqrt{m})\) nodes. If \(G\) has uniformly bounded vertex degrees, we show the separator is found by spectral partitioning.

A string graph is the intersection graph of continuous arcs in the plane. The preceding result implies that every string graph with m edges has a balanced separator of size \(O(\sqrt{m})\). This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010) and improves over the \(O(\sqrt{m} \log m)\) bound of Matousek (2013).

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than \(2^{n^c}\), for some constant \(c > 0\). This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.

Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.

[ PPT slides ]

Best paper award, STOC 2015

We study the computational power of general symmetric relaxations for combinatorial optimization problems, both in the linear programming (LP) and semidefinite programming (SDP) case. We show new connections to explicit LP and SDP relaxations, like those obtained from standard hierarchies.

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.

Video: Linear programming and constraint satisfaction (Simons Institute)

The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal c > 0, if the node cut conditions are satisfied, then one can simultaneously route a c-fraction of all the demands.

This answers an open question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of multi-commodity polymatroid networks introduced by Chekuri, et. al. Our approach employs a new type of random metric embedding in order to round the convex programs corresponding to these more general flow problems.

We study the quantitative geometry of graphs in terms of their genus, using the structure of certain cut graphs. These are subgraphs whose removal leaves a planar graph.

Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$ can be probabilistically embedded into a graph of genus $g−1$ with constant distortion. Viewing a graph of genus $g$ as embedded on the surface of a sphere with $g$ handles attached, Indyk and Sidiropoulos’ method gives an embedding into a distribution over planar graphs with distortion $O(g)$ by iteratively removing the handles. By removing all g handles at once, we present a probabilistic embedding with distortion $O(g^2)$ for both orientable and non-orientable graphs. Our result is obtained by showing that the nimum-cut graph of Erickson and Har Peled (2004) has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma of Lee and Sidiropoulos (2009).

We consider questions about vertex cuts in graphs, random walks in metric spaces, and dimension reduction in $\ell_1$ and $\ell_2$; these topics are intimately connected because they can each be reduced to the existence of various families of real-valued Lipschitz maps on certain metric spaces. We view these issues through the lens of shortest-path metrics on series-parallel graphs, and we discuss the implications for a variety of well-known open problems.

We prove that the function \(d : \mathbb{R}^3 \times \mathbb{R}^3 \to [0,\infty)\) given by

is a metric on \(\mathbb{R}^3\) such that \((\mathbb{R}^3, \sqrt{d})\) is isometric to a subset of Hilbert space, yet \((\mathbb{R}^3,d)\) does not admit a bi-Lipschitz embedding into \(L_1\). This yields a new simple counter example to the Goemans-Linial conjecture on the integrality gap of the SDP relaxation of the Sparsest Cut problem.

Our methods involve Fourier analytic techniques, combined with a breakthrough of Cheeger and Kleiner, along with classical results of Pansu on the differentiability of Lispchitz functions on the Heisenberg group.

We present an $O(\sqrt{\log n} \log \log n)$ upper bound on the $(n-1)$-dimensional volume distortion of $n$-point subsets of a Euclidean space, nearly resolving the main open questions of [Dunagan-Vempala 2001] and [Krauthgamer-Linial-Magen 2004]. The best previous bound was $O(\log n)$ and our bound is nearly tight, as even the $2$-dimensional volume distortion of an $n$-vertex path is $\Omega(\sqrt{\log n})$.

We explore approximation algorithms on negatively curved metric spaces in the sense of Gromov. For instance, we show that the Traveling Salesman Problem admits a PTAS when the set of points lies in hyperbolic $d$-space.

We observe that combining the techniques behind the Sparsest Cut SDP analysis of Arora, Rao, and Vazirani, with the rounding algorithm of Rao and Richa yields an $O(\sqrt{\log n} \log \log n)$-approximation for the minimum linear arrangement problem, improving over the previous bound of $O(\log n)$.

We prove that every \(n\)-point metric space of negative type (and, in particular, every \(n\)-point subset of \(L_1\)) embeds into a Euclidean space with distortion \(O(\sqrt{\log n} \log \log n)\), a result which is tight up to the iterated logarithm factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a set of size \(k\), we achieve an approximation ratio of \(O(\sqrt{\log k} \log \log k)\).

We develop the algorithmic theory of vertex separators, and its relation to embeddings of certain metric spaces. As a consequence, we obtain an \(O(\sqrt{\log n})\)-approximation for min-ratio vertex cuts in general graphs based on a new SDP relaxation and a tight analysis of its integrality gap.

Our results allow yield algorithms for constructing approximately optimal tree decompositions of graphs. If a graph has treewidth \(k\), we find a tree decomposition of width at most \(O(k \sqrt{\log k})\). If, additionally, the input graph excludes a fixed graph as a minor, we produce a tree decomposition of width \(O(k)\).

Related: A similar method gives improved bounds for the minimum linear arrangement problem.

[Note: This is the (unpublished) full version of a paper appearing in the SODA 2005 conference under the name Distance scales, embeddings, and efficient relaxations of the cut cone.]

We introduce a new number of new techniques for the construction of low-distortion embeddings of a finite metric space. These include a generic Gluing Lemma which avoids the overhead typically incurred from the naı̈ve concatenation of maps for different scales of a space. We also give a significantly improved and quantitatively optimal version of the main structural theorem of Arora, Rao, and Vazirani on separated sets in metrics of negative type. The latter result offers a simple hyperplane rounding algorithm for the computation of an \(O(\sqrt{\log n})\)-approximation to the Sparsest Cut problem with uniform demands, and has a number of other applications to embeddings and approximation algorithms.

For a more elegant and simpler proof of the “Big Core” Theorem, one can consult these notes of Rothvoss.

This paper establishes that a metric space $X$ supports approximate nearest-neighbor queries against any $n$-point subset with at most $\mathrm{poly}(\log n)$ query time if and only if one has certain quantitative estimates on the doubling constant of $n$-point subsets.

We present simple deterministic data structures for maintaining a set of points in a metric space under insertions and deletions, with the ability to make fast nearest-neighbor queries. The running-time of the operations scales with the doubling constant of the underlying metric space.

We study the quantitative ditsortion required to embed finite, uniformly doubling metric spaces into normed spaces.

We establish lower bounds on the polynomial-time approximability of the vertex-connectivity variant of the Survivable Network Design Problem (SNDP) under the assumption that \(\mathsf{NP}\) does not have quasipolynomial-time algorithms. Some related hardness of approximation results are established, e.g., for the edge and vertex-connectivity augmention problems.