We give an \(O((\log k)^6)\)-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 determinsitic algorithms. The approach is via reduction to potential-based algorithms for the fractional k-server problem on ultrametrics.

[ abs |
bib
]
k-server via multiscale entropic regularization,
with S. Bubeck, M. B. Cohen, Y. T. Lee, and A. Madry (To appear, STOC 2018)

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\).

[ abs |
bib
]
Discrete uniformizing metrics on distributional limits of sphere packings
(To appear, GAFA)

[ abs |
bib
]
Conformal growth rates and spectral geometry on distributional limits of graphs
(preprint, 2017)

[credit: Jérémie Bettinelli]

For a unimodular random graph \((G, \rho)\), we consider deformations of its intrinsic path metric by a (random) weighting of its vertices. This leads to the notion of the conformal growth exponent of \((G, \rho)\), which is the best asymptotic degree of volume growth of balls that can be achieved by such a weighting. Under moment conditions on the degree of the root, we show that the conformal growth exponent of a unimodular random graph bounds its almost sure spectral dimension.

For two-dimensional growth, one obtains more precise information about recurrence, the heat kernel, and subdiffusivity of the random walk. In particular, this gives a new method for studying the uniform infinite planar triangulation (UIPT) and quadrangulation (UIPQ).

[ abs |
bib
]
Diffusive estimates for random walks on stationary random graphs of polynomial growth,
with S. Ganguly and Y. Peres (GAFA, 2017)

We show that if $(G,\rho)$ is a stationary random graph of annealed polynomial growth, then almost surely there is an infinite sequence of times at which the random walk started from x is at most diffusive. This result is new even in the case when G is a stationary random subgraph of $\mathbb{Z}^d$. Combined with the work of Benjamini, Duminil-Copin, Kozma, and Yadin, it implies that G almost surely does not admit a non-constant harmonic function of sublinear growth.

To complement this, we argue that passing to a subsequence of times is necessary, as there are stationary random graphs of (almost sure) polynomial growth where the random walk is almost surely superdiffisuve at an infinite subset of times.

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).

[ abs |
bib
]
Transport-entropy inequalities and curvature for discrete-space Markov chains,
with R. Eldan and J. Lehec (Matousek, 2017)

[ abs |
bib
]
Lower bounds on the size of semidefinite programming relaxations,
with P. Raghavendra and D. Steurer (STOC'15)

[credit: Bernd Sturmfels]

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**

[ abs |
bib
]
Regularization under diffusion and anti-concentration of the information content,
with R. Eldan (FOCS'15; Duke)

We show that under the Ornstein-Uhlenbeck semigroup (i.e., the natural diffusion process) on n-dimensional Gaussian space, any nonnegative, measurable function exhibits a uniform tail bound better than that implied by Markov’s inequality and conservation of mass. This confirms positively the Gaussian limiting case of Talagrand’s convolution conjecture (1989).

Video: Talagrand’s convolution conjecture and geometry via coupling (IAS)

[ abs |
bib
]
A Gaussian upper bound for martingale small-ball probabilities,
with Y. Peres and C. K. Smart (Ann. Prob., 2016)

[ abs |
bib
]
Approximate constraint satisfaction requires large LP relaxations,
with S. O. Chan, P. Raghavendra, and D. Steurer (FOCS'13; JACM)

[credit: Fiorini, Rothvoss, and Tiwary]

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)

[ abs |
bib
]
Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements,
with F. G. S. L. Brandao, A. W. Harrow, and Y. Peres (ITCS'14)

Recall the classical hypothesis testing setting with two convex sets of probability distributions $P$ and $Q$. One receives either $n$ i.i.d. samples from a distribution $p \in P$ or from a distribution $q \in Q$ and wants to decide from which set the points were sampled. It is known that the optimal exponential rate at which errors decrease can be achieved by a simple maximum-likelihood ratio test which does not depend on $p$ or $q$, but only on the sets $P$ and $Q$. We consider an adaptive generalization of this model where the choice of $p \in P$ and $q \in Q$ can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the $k$th round, an adversary, having observed all the previous samples in rounds $1,…,k-1$, chooses $p_k \in P$ and $q_k \in Q$, with the goal of confusing the hypothesis test. We prove that even in this case, the optimal exponential error rate can be achieved by a simple maximum-likelihood test that depends only on $P$ and $Q$.

We then show that the adversarial model has applications in hypothesis testing for quantum states using restricted measurements. For example, it can be used to study the problem of distinguishing entangled states from the set of all separable states using only measurements that can be implemented with local operations and classical communication (LOCC). The basic idea is that in our setup, the deleterious effects of entanglement can be simulated by an adaptive classical adversary. We prove a quantum Stein’s Lemma in this setting: In many circumstances, the optimal hypothesis testing rate is equal to an appropriate notion of quantum relative entropy between two states. In particular, our arguments yield an alternate proof of Li and Winter’s recent strengthening of strong subadditivity for quantum relative entropy.

[ abs |
bib
]
A lower bound for dimension reduction of trees in $\ell_1$,
with M. Moharrami (unpublished, 2013)

[ abs |
bib
]
A node-capacitated Okamura-Seymour theorem,
with M. Mendel and M. Moharrami (STOC'13; Math. Prog. Ser. A.)

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.

For two metric spaces $X$ and $Y$, say that $X$ *threshold-embeds into $Y$*
if there exist a number $K > 0$ and a family of
Lipschitz maps $\{\varphi_{\tau} : X \to Y : \tau > 0 \}$
such that for every $x,y \in X$,
\[d_X(x,y) \geq \tau \implies d_Y(\varphi_{\tau}(x),\varphi_{\tau}(y)) \geq \|\varphi_{\tau}\|_{\mathrm{Lip}} \frac{\tau}{K},\]
where $\|\varphi_{\tau}\|_{\mathrm{Lip}}$
denotes the Lipschitz constant of $\varphi_{\tau}$.

We show that if a metric space $X$ threshold-embeds into a Hilbert space, then $X$ has Markov type 2. As a consequence, planar graph metrics and doubling metrics have Markov type 2, answering questions of Naor, Peres, Schramm, and Sheffield. More generally, if a metric space $X$ threshold-embeds into a $p$-uniformly smooth Banach space, then $X$ has Markov type $p$. Our results suggest some non-linear analogs of Kwapien’s theorem. For instance, a subset $X \subseteq L_1$ threshold-embeds into Hilbert space if and only if $X$ has Markov type 2.

[ abs |
bib
]
On the Hausdorff dimension of ultrametric subsets in \(\mathbb{R}^n\),
with M. Mendel and M. Moharrami (Fund. Math., 2012)

[ abs |
bib
]
Multi-way spectral partitioning and higher-order Cheeger inequalities,
with S. Oveis-Gharan and L. Trevisan (STOC'12; JACM)

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger’s inequality and its variants provide a robust version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero.

It has been conjectured that an analogous characterization holds for higher multiplicities: There are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. We resolve this conjecture positively. Our result provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into \(\mathbb{R}^k\), and then apply geometric considerations to the embedding. We also show that these techniques yield a nearly optimal quantitative connection between the expansion of sets of measure ≈ 1/k and the kth smallest eigenvalue of the normalized Laplacian.

Notes: A no frills proof of the higher-order Cheeger inequality

Related: One hundred hours of lectures from the SGT program at the Simons Institute.

Related: Laurent Miclo uses the higher-order Cheeger inequality for the basis of his resolution of Hoegh-Krohn and Simon’s conjecture that every hyperbounded operator has a spectral gap.

[ abs |
bib
]
Dimension reduction for finite trees in $\ell_1$,
with A. de Mesmay and M. Moharrami (SODA'12; DCG)

[ abs |
bib
]
Cover times, blanket times, and majorizing measures,
with J. Ding and Y. Peres (STOC'11; Ann. Math.)

We show that the cover time of a graph can be related to the square of the maximum of the associated Gaussian free field. This yields a positive answer to a question of Aldous and Fill (1994) on deterministic approximations to the cover time, and positively resolves the Blanket Time conjecture of Winkler and Zuckerman (1996).

Video: Cover times of graphs and the Gaussian free field (Newton Institute)

Notes: Majorizing measures and Gaussian processes

Related questions and conjectures (all solved except the one after Lemma 4)

See also the related preprint of Alex Zhai that resolves our main conjecture.

[ abs |
bib
]
Harmonic maps on amenable groups and a diffusive lower bound for random walks,
with Y. Peres (Ann. Prob., 2013)

[ abs |
bib
]
On the optimality of gluing over scales,
with A. Jaffe and M. Moharrami (APPROX'09, DCG)

We show that for every $\alpha > 0$, there is an $n$-point metric space $(X,d)$ where every “scale” admits a Euclidean embedding with distortion at most $\alpha$, but any bi-Lipschitz embedding requires distortion $\Omega(\sqrt{\alpha \log n})$.

The matching upper bound was known to be tight at both endpoints (when $\alpha \asymp 1$ and $\alpha \asymp \log n$, but nowhere in between). This also shows that the “measured descent” method has an optimal asymptotic dependence on the parameters.

*cut graphs*.
These are subgraphs whose removal leaves a planar graph.

[ abs |
bib
]
Randomly removing $g$ handles at once,
with G. Borradaile and A. Sidiropoulos (SoCG'09; CGTA)

[ abs |
bib
]
Metric uniformization and spectral bounds for graphs,
with J. A. Kelner, G. N. Price, and S.-H. Teng (STOC'09; GAFA)

We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate “Riemannian” metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs.

We use our method to show that for any positive integer k, the kth smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k=2.

[ abs |
bib
]
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows,
with P. Biswal and S. B. Rao (FOCS'08; JACM)

A method is presented for establishing an upper bound on the first non-trivial eigenvalue of the Laplacian of a finite graph. Our approach uses multi-commodity flows to deform the geometry of the graph, and the resulting metric is embedded into Euclidean space to recover a bound on the Rayleigh quotient.

Using this, we resolve positively a question of Spielman and Teng by proving that \(\lambda_2(G) \leq O(d h^6 \log h/n)\) whenever \(G\) is a \(K_h\)-minor-free graph with maximum degree \(d\). While the standard “sweep” algorithm applied to the second eigenvector of a graph my fail to find a good quotient cut in graphs of unbounded degree, the arguments here produce a vector that works for arbitrary graphs. This yields an alterante proof of the Alon-Seymour-Thomas theorem that every excluded-minor family of graphs has \(O(\sqrt{n})\)-node balanced separators.

Related: These methods are extended to higher eigenvalues in a
joint work with Kelner, Price, and Teng.

Related: These method form the basis for the uniformization and heat kernel bounds in Conformal
growth rates and spectral geometry on distributional limits of graphs.

[ abs |
bib
]
Eigenvectors of random graphs: Nodal domains,
with Y. Dekel and N. Linial (RANDOM'07; RS&A)

We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known about the corresponding eigenvectors. Our main focus in this paper is on the nodal domains associated with the different eigenfunctions. In the analogous realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. Graphical nodal domains turn out to have interesting and unexpected properties.

Our main theorem asserts that there is a constant c such that for almost every graph G, each eigenfunction of G has at most two large nodal domains, and in addition at most c exceptional vertices outside these primary domains. We also discuss variations of these questions and briefly report on some numerical experiments which, in particular, suggest that almost surely there are just two nodal domains and no exceptional vertices.

Let $G$ be a finite group with symmetric generating set $S$, and let $c = \max_{R > 0} |B(2R)|/|B(R)|$ be the doubling constant of the corresponding Cayley graph, where $B(R)$ denotes an $R$-ball in the word-metric with respect to $S$. We show that the multiplicity of the $k$th eigenvalue of the Laplacian on the Cayley graph of $G$ is bounded by a function of only $c$ and $k$. More specifically, the multiplicity is at most $\exp((\log c)(\log c + \log k))$. Similarly, if $X$ is a compact, $n$-dimensional Riemannian manifold with non-negative Ricci curvature, then the multiplicity of the $k$th eigenvalue of the Laplace-Beltrami operator on $X$ is at most $\exp(n^2 + n \log k)$.

The first result (for $k=2$) yields the following group-theoretic application. There exists a normal subgroup $N$ of $G$, with $[G : N] \leq \alpha(c)$, and such that $N$ admits a homomorphism onto the cyclic group $Z_M$, where $M \geq |G|^{\delta(c)}$ and $\alpha(c), \delta(c) > 0$ are explicit functions depending only on $c$. This is the finitary analog of a theorem of Gromov which states that every infinite group of polynomial growth has a subgroup of finite index which admits a homomorphism onto the integers.

This addresses a question of Trevisan, and is proved by scaling down Kleiner’s proof of Gromov’s theorem. In particular, we replace the space of harmonic functions of fixed polynomial growth by the second eigenspace of the Laplacian on the Cayley graph of $G$.

[ abs |
bib
]
Coarse differentiation and multi-flows in planar graphs,
with P. Raghavendra (APPROX'07; DCG)

*coarse differentiation*
methodology of Eskin, Fisher, and Whyte.

[ abs |
bib
]
Almost Euclidean subspaces of $\ell_1^n$ via expander codes,
with V. Guruswami and A. Razborov (SODA'08; Combinatorica)

We give an explicit construction of subspaces $X \subseteq \mathbb{R}^N$ of dimension $(1-o(1)) N$ such that for every $x \in X$,

$$(\log N)^{-O(\log \log \log N)} \|x\|_2 \leq \frac{\|x\|_1}{\sqrt{N}} \leq \|x\|_2\,.$$

Through known connections between such Euclidean sections of $\ell_1$ and compressed sensing matrices, our result also gives explicit compressed sensing matrices for low compression factors for which basis pursuit is guaranteed to recover sparse signals. Our construction makes use of unbalanced bipartite graphs to impose local linear constraints on vectors in the subspace, and our analysis relies on expansion properties of the graph. This is inspired by similar constructions of error-correcting codes.

[ abs |
bib
]
Euclidean sections of $\ell_1^n$ with sublinear randomness and error-correction over the reals,
with V. Guruswami and A. Wigderson (RANDOM'08)

It is well-known that $\mathbb{R}^N$ has has subspaces of dimension proportional to $N$ on which the $\ell_1$ and $\ell_2$ norms are uniformly equivalent, but it is unknown how to construct them explicitly. We show that, for any $\delta > 0$, such a subspace can be generated using only $N^{\delta}$ random bits. This improves over previous constructions of Artstein-Avidan and Milman, and of Lovett and Sodin, which require $O(N log N)$, and $O(N)$ random bits, respectively.

It is known that such subspaces give rise to error-correcting codes over the reals and compressed sensing matrices. As in the work of Guruswami, Lee, and Razborov, our construction is the continuous analog of a Tanner code, and makes use of expander graphs to impose a collection of local linear constraints on vectors in the subspace. Our analysis is able to achieve uniform equivalence of the $\ell_1$ and $\ell_2$ norms (independent of the dimension). It has parallels to iterative decoding of Tanner codes, and leads to an analogous near-linear time algorithm for error-correction over reals.

[ abs |
bib
]
\(L_p\) metrics on the Heisenberg group and the Goemans-Linial conjecture,
with A. Naor (FOCS'06)

[credit: Patrick Massot]

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

\begin{align*}
d(&(x,y,z),(t,u,v)) \\ &=
\left(\left[\left((t-x)^2+(u-y)^2\right)^2 + (v-z+2xu-2yt)^2\right]^{1/2} + (t-x)^2 + (u-y)^2\right)^{1/2}
\end{align*}

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.

[ abs |
bib
]
An improved approximation ratio for the minimum linear arrangement problem,
with U. Feige (IPL 2007)

[ abs |
bib
]
Improved approximation algorithms for minimum-weight vertex separators,
with M.-T. Hajiaghayi and U. Feige (STOC'05; SICOMP)

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.

[ abs |
bib
]
Metric structures in $\ell_1$: Dimension, snowflakes, and average distortion
(Europ. J. Combin., 2005)

[ abs |
bib
]
Measured descent: A new embedding method for finite metrics,
with R. Krauthgamer, M. Mendel, and A. Naor (FOCS'04; GAFA)

*measured descent*
and use it to resolve a number of open questions in the theory of embeddings
of finite metric spaces.

[ abs |
bib
]
Extending Lipschitz functions via random metric partitions,
with A. Naor (Math. Invent., 2005)

Many classical problems in geometry and analysis involve the gluing together of local information to produce a coherent global picture. Inevitably, the difficulty of such a procedure lies at the local boundary, where overlapping views of the same locality must somehow be merged. It is therefore desirable that the boundaries be “smooth,” allowing a graceful transition from one viewpoint to the next. For instance, one may point to Whitney’s use of partitions of unity in studying what is now known as the Whitney extension problem.

In the present work, we consider what is perhaps the most basic Whitney-type extension problem, that of extending a Lipschitz function so that it remains Lipschitz. Often such a map is extended by first producing a cover of the new domain, extending the mapping locally, and then gluing together the individual pieces. Our main observation is that in many cases, if one chooses a random cover from the right distribution, the boundary can be made “smooth” on average, even when the local maps are individually quite coarse. This insight leads to the unification, generalization, and improvement of many known results, as well as to new results for many interesting spaces.

[ abs |
bib
]
The black-box complexity of nearest-neighbor search,
with R. Krauthgamer (ICALP'04; TCS)

Announcement of Extending Lipschitz functions via random metric partitions.

[ abs |
bib
]
Navigating nets: Simple algorithms for proximity search,
with R. Krauthgamer (SODA'04)

[ abs |
bib
]
Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\),
with A. Naor (GAFA, 2004)

[ abs |
bib
]
Hardness of approximation for vertex-connectivity network design problems,
with G. Kortsarz and R. Krauthgamer (APPROX'02, SICOMP)