# Publications

#### [chronological]

Indexing in progress (see my recent preprints on the arxiv)
[ abs | ]   Spectral hypergraph sparsification via chaining (preprint, 2022)

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

[ abs | ]   Spectral dimension, metric embeddings, and the Euclidean growth exponent (preprint, 2022)

For reversible random networks, we exhibit a relationship between the almost sure spectral dimension and the Euclidean growth exponent, which is the smallest asymptotic rate of volume growth over all embeddings of the network into a Hilbert space. Using metric embedding theory, it is then shown that the Euclidean growth exponent coincides with the metric growth exponent. This simplifies and generalizes a powerful tool for bounding the spectral dimension in random networks.

[ abs | bib ]   Multiscale entropic regularization for MTS on general metric spaces, with F. Ebrahimnejad (ITCS'22)

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

@inproceedings{EL22,
AUTHOR = {Farzam Ebrahimnejad and James R. Lee},
BIBSOURCE = {dblp computer science bibliography, https://dblp.org},
BOOKTITLE = {13th Innovations in Theoretical Computer Science Conference, {ITCS}
2022, January 31 - February 3, 2022, Berkeley, CA,
{USA}},
DOI = {10.4230/LIPIcs.ITCS.2022.60},
EDITOR = {Mark Braverman},
PAGES = {60:1--60:21},
PUBLISHER = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
SERIES = {LIPIcs},
TIMESTAMP = {Wed, 26 Jan 2022 14:53:11 +0100},
TITLE = {Multiscale Entropic Regularization for {MTS} on General Metric
Spaces},
URL = {https://doi.org/10.4230/LIPIcs.ITCS.2022.60},
VOLUME = {215},
YEAR = {2022}
}

[ abs | ]   Non-existence of annular separators in geometric graphs, with F. Ebrahimnejad (To appear, DCG)

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

[ abs | ]   Relations between scaling exponents in unimodular random graphs (preprint, 2020)

We investigate the validity of the “Einstein relations” in the general setting of unimodular random networks. These are equalities relating scaling exponents:

\begin{align*} d_w &= d_f + \tilde{\zeta} \\ d_s &= 2d_f/d_w, \end{align*}

where $d_w$ is the walk dimension, $d_f$ is the fractal dimension, $d_s$ is the spectral dimension, and $\tilde{\zeta}$ is the resistance exponent. Roughly speaking, this relates the mean displacement and return probability of a random walker to the density and conductivity of the underlying medium. We show that if $d_f$ and $\tilde{\zeta} \geq 0$ exist, then $d_w$ and $d_s$ exist, and the aforementioned equalities hold. Moreover, our primary new estimate $d_w \geq d_f + \tilde{\zeta}$ is established for all $\tilde{\zeta} \in \mathbb{R}$.

This has a number of consequences for unimodular random networks arising from statistical physics.

[ abs | bib ]   Chemical subdiffusivity of critical 2D percolation, with S. Ganguly (Comm. Math. Phys., 2022)

We show that random walk on the incipient infinite cluster (IIC) of two-dimensional critical percolation is subdiffusive in the chemical distance (i.e., in the intrinisc graph metric). Kesten (1986) famously showed that this is true for the Euclidean distance, but it is known that the chemical distance is typically asymptotically larger.

More generally, we show that subdiffusivity in the chemical distance holds for stationary random graphs of polynomial volume growth, as long as there is a multiscale way of covering the graph so that “deep patches” have “thin backbones.” Our estimates are quantitative and give explicit bounds in terms of the one and two-arm exponents.

@article{GL22,
AUTHOR = {Ganguly, Shirshendu and Lee, James R.},
FJOURNAL = {Communications in Mathematical Physics},
JOURNAL = {Comm. Math. Phys},
NUMBER = {2},
PAGES = {695--714},
TITLE = {Chemical subdiffusivity of critical {2D} percolation},
VOLUME = {389},
YEAR = {2022}
}

[ abs | bib ]   On planar graphs of uniform polynomial growth, with F. Ebrahimnejad (PTRF, 2021)

Consider an infinite planar graph with uniform polynomial growth of degree $d > 2$. Many examples of such graphs exhibit similar geometric and spectral properties, and it has been conjectured that this is necessary. We present a family of counterexamples. In particular, we show that for every rational $d > 2$, there is a planar graph with uniform polynomial growth of degree $d$ on which the random walk is transient, disproving a conjecture of Benjamini (2011).

By a well-known theorem of Benjamini and Schramm, such a graph cannot be a unimodular random graph. We also give examples of unimodular random planar graphs of uniform polynomial growth with unexpected properties. For instance, graphs of (almost sure) uniform polynomial growth of every rational degree $d > 2$ for which the speed exponent of the walk is larger than $1/d$, and in which the complements of all balls are connected. This resolves negatively two questions of Benjamini and Papasoglou (2011).

@article{EL21,
AUTHOR = {Ebrahimnejad, Farzam and Lee, James R.},
FJOURNAL = {Probability Theory and Related Fields},
JOURNAL = {Probab. Theory Relat. Fields},
NUMBER = {3},
PAGES = {955--984},
TITLE = {On planar graphs of uniform polynomial growth},
VOLUME = {180},
YEAR = {2021}
}

[ abs | bib ]   Pure entropic regularization for metrical task systems, with C. Coester (COLT'19)

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.

@inproceedings{CL19,
AUTHOR = {Christian Coester and James R. Lee},
BOOKTITLE = {Conference on Learning Theory, {COLT} 2019, 25-28 June 2019,
Phoenix, AZ, {USA}},
PAGES = {835--848},
TITLE = {Pure entropic regularization for metrical task systems},
YEAR = {2019}
}

[ abs | bib ]   Metrical task systems on trees via mirror descent and unfair gluing, with S. Bubeck, M. B. Cohen, and Y. T. Lee (SODA'19; SICOMP)

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.

@article{BCLL21,
AUTHOR = {Bubeck, S\'{e}bastien and Cohen, Michael B. and Lee, James R. and
Lee, Yin Tat},
FJOURNAL = {SIAM Journal on Computing},
ISSN = {0097-5397},
JOURNAL = {SIAM J. Comput.},
NUMBER = {3},
PAGES = {909--923},
TITLE = {Metrical task systems on trees via mirror descent and unfair
gluing},
VOLUME = {50},
YEAR = {2021}
}

[ abs | bib ]   Flow-cut gaps and face covers in planar graphs, with R. Krauthgamer and H. Rika (SODA'19)

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.

@inproceedings{KLR19,
AUTHOR = {Krauthgamer, Robert and Lee, James R. and Rika, Havana},
BOOKTITLE = {Proceedings of the {T}hirtieth {A}nnual {ACM}-{SIAM} {S}ymposium on
{D}iscrete {A}lgorithms},
PAGES = {525--534},
TITLE = {Flow-cut gaps and face covers in planar graphs},
YEAR = {2019}
}


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.

@incollection{LeeFOCS18,
AUTHOR = {Lee, James R.},
BOOKTITLE = {59th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer
{S}cience---{FOCS} 2018},
PAGES = {438--449},
PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA},
TITLE = {Fusible {HST}s and the randomized {$k$}-server conjecture},
YEAR = {2018}
}

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

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

@inproceedings{BCLLM18,
author    = {S{\'{e}}bastien Bubeck and
Michael B. Cohen and
Yin Tat Lee and
James R. Lee and
title     = {k-server via multiscale entropic regularization},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages     = {3--16},
year      = {2018},
}


If $(G, \rho)$ is the distributional limit of finite graphs that can be sphere-packed in $\mathbb{R}^d$, then the conformal growth exponent of $(G, \rho)$ is at most d. In other words, there exists a unimodular “unit volume” weighting of the graph metric on G such that the volume growth of balls is asymptotically polynomial with exponent d. This generalizes to graphs that can be quasisymmetrically packed in an Ahlfors d-regular metric measure space. Using our previous work, it gives bounds on the almost sure spectral dimension of G.

@article{LeeGAFA18,
AUTHOR = {Lee, James R.},
FJOURNAL = {Geometric and Functional Analysis},
JOURNAL = {Geom. Funct. Anal.},
NUMBER = {4},
PAGES = {1091--1130},
TITLE = {Discrete uniformizing metrics on distributional limits of sphere
packings},
VOLUME = {28},
YEAR = {2018}
}


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

@article{LeeAOP21,
AUTHOR = {James R. Lee},
DOI = {10.1214/20-AOP1480},
FJOURNAL = {Annals of Probability},
ISSN = {0091-1798},
JOURNAL = {Ann. Probab.},
NUMBER = {6},
PAGES = {2671-2731},
TITLE = {Conformal growth rates and spectral geometry on distributional
limits of graphs},
VOLUME = {49},
YEAR = {2021}
}

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

Addendum: In the paper, we ask whether passing to a subsequence of times is necessary when $G$ is a stationary random subgraph of $\mathbb{Z}^d$. For the case $d=2$, it holds for all times using my paper with Ding and Peres. For $d$ sufficiently large, passing to a subsequence of times is necessary; this can be proved by showing that our stationary random graph occurs as a stationary random subgraph of $\mathbb{Z}^d_{\infty}$, using my paper with Krauthgamer.

@article {GLP17,
AUTHOR = {Ganguly, Shirshendu and Lee, James R. and Peres, Yuval},
TITLE = {Diffusive estimates for random walks on stationary random
graphs of polynomial growth},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {27},
YEAR = {2017},
NUMBER = {3},
PAGES = {596--630},
}

[ abs | bib ]   Separators in region intersection graphs (ITCS'17)

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

@inproceedings{LeeStrings17,
author    = {James R. Lee},
title     = {Separators in Region Intersection Graphs},
booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
2017, January 9-11, 2017, Berkeley, CA, {USA}},
pages     = {1:1--1:8},
year      = {2017},
}

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

We show that if the random walk on a graph has positive coarse Ricci curvature in the sense of Ollivier, then the stationary measure satisfies a $W^1$ transport-entropy inequality. Peres and Tetali have conjectured a stronger consequence, that a modified log-Sobolev inequality (MLSI) should hold, in analogy with the setting of Markov diffusions. We discuss how our entropy interpolation approach suggests a natural attack on the MLSI conjecture.

@incollection {ELL17,
AUTHOR = {Eldan, Ronen and Lee, James R. and Lehec, Joseph},
TITLE = {Transport-entropy inequalities and curvature in discrete-space
{M}arkov chains},
BOOKTITLE = {A journey through discrete mathematics},
PAGES = {391--406},
PUBLISHER = {Springer},
YEAR = {2017},
}

[ abs | bib ]   Covering the large spectrum and generalized Riesz products (SIDMA, 2016)

Entropy-regularized gradient descent is used to reprove some results from additive combinatorics on the structure of the large Fourier spectrum of dense subsets of the integers.

@article {LeeSpectrum17,
AUTHOR = {Lee, James R.},
TITLE = {Covering the large spectrum and generalized {R}iesz products},
JOURNAL = {SIAM J. Discrete Math.},
FJOURNAL = {SIAM Journal on Discrete Mathematics},
VOLUME = {31},
YEAR = {2017},
NUMBER = {1},
PAGES = {562--572},
}

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

Best paper award, STOC 2015

@inproceedings{LRS15,
AUTHOR = {James R. Lee and Prasad Raghavendra and David Steurer},
BOOKTITLE = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June
14-17, 2015},
NOTE = {Full version at \verb|https://arxiv.org/abs/1411.6317|},
PAGES = {567--576},
TITLE = {Lower Bounds on the Size of Semidefinite Programming Relaxations},
YEAR = {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).

@article{ElDuke18,
AUTHOR = {Eldan, Ronen and Lee, James R.},
FJOURNAL = {Duke Mathematical Journal},
JOURNAL = {Duke Math. J.},
NUMBER = {5},
PAGES = {969--993},
TITLE = {Regularization under diffusion and anticoncentration of the
information content},
VOLUME = {167},
YEAR = {2018}
}

[ abs | bib ]   On the power of symmetric LP and SDP relaxations, with P. Raghavendra, D. Steurer, and N. Tan (CCC'14)

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.

@inproceedings{DBLP:conf/coco/LeeRST14,
author    = {James R. Lee and
David Steurer and
Ning Tan},
title     = {On the Power of Symmetric {LP} and {SDP} Relaxations},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
pages     = {13--21},
year      = {2014},
}

[ abs | bib ]   A Gaussian upper bound for martingale small-ball probabilities, with Y. Peres and C. K. Smart (Ann. Prob., 2016)
Consider a discrete-time martingale $\{X_t\}$ taking values in a Hilbert space $\mathcal H$. We show that if for some $L \geq 1$, the bounds $\mathbb{E} \left[\|X_{t+1}-X_t\|_{\mathcal H}^2 \mid X_t\right]=1$ and $\|X_{t+1}-X_t\|_{\mathcal H} \leq L$ are satisfied for all times $t \geq 0$, then there is a constant $c = c(L)$ such that for $1 \leq R \leq \sqrt{t}$, $\mathbb{P}(\|X_t\|_{\mathcal H} \leq R \mid X_0 = x_0) \leq c \frac{R}{\sqrt{t}} e^{-\|x_0\|_{\mathcal H}^2/(6 L^2 t)}\,$ $\mathbb{P}(\|X_t-X_0\|_{\mathcal H} \leq R) \leq c \frac{R}{\sqrt{t}}\,.$ Following [Lee-Peres, Ann. Probab. 2013], this estimate has applications to small-ball estimates for random walks on vertex-transitive graphs: We show that for every infinite, connected, vertex-transitive graph $G$ with bounded degree, there is a constant $C_G > 0$ such that if $\{Z_t\}$ is the simple random walk on $G$, then for every $\varepsilon > 0$ and $t \geq 1/\varepsilon^2$, $$\mathbb{P}\left(\vphantom{\bigoplus}\mathrm{dist}_G(Z_t,Z_0) \leq \varepsilon \sqrt{t}\right) \leq C_G\, \varepsilon\,,$$ where $\mathrm{dist}_G$ denotes the graph distance in $G$.
@article {LPS16,
AUTHOR = {Lee, James R. and Peres, Yuval and Smart, Charles K.},
TITLE = {A {G}aussian upper bound for martingale small-ball
probabilities},
JOURNAL = {Ann. Probab.},
FJOURNAL = {The Annals of Probability},
VOLUME = {44},
YEAR = {2016},
NUMBER = {6},
PAGES = {4184--4197},
}

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

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)

@article {CLRS16,
AUTHOR = {Chan, Siu On and Lee, James R. and Raghavendra, Prasad and
Steurer, David},
TITLE = {Approximate constraint satisfaction requires large {LP}
relaxations},
JOURNAL = {J. ACM},
FJOURNAL = {Journal of the ACM},
VOLUME = {63},
YEAR = {2016},
NUMBER = {4},
PAGES = {Art. 34, 22},
}

[ 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 (IEEE TIT; 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.

@article{BHLP20,
author    = {F. G. S. L. {Brandão} and A. W. {Harrow} and J. R. {Lee} and Y. {Peres}},
journal   = {IEEE Transactions on Information Theory},
title     = {Adversarial Hypothesis Testing and a Quantum Stein’s Lemma for Restricted Measurements},
year      = {2020},
volume    = {66},
number    = {8},
pages     = {5037-5054},
}
@inproceedings{BHLP14,
author    = {Fernando G. S. L. Brand{\~{a}}o and
Aram Wettroth Harrow and
James R. Lee and
Yuval Peres},
title     = {Adversarial hypothesis testing and a quantum stein's lemma for restricted
measurements},
booktitle = {Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ,
USA, January 12-14, 2014},
pages     = {183--194},
year      = {2014},
}

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

There is a constant c > 0 such that for every $\varepsilon \in (0,1)$ and $n \geq 1/\varepsilon^2$, the following holds. Any mapping from the $n$-point star metric into $\ell_1^d$ with bi-Lipschitz distortion $1+\varepsilon$ requires dimension $d \geq \frac{c \log n}{\varepsilon^2 \log (1/\varepsilon)}.$

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

@article {LMM15,
AUTHOR = {Lee, James R. and Mendel, Manor and Moharrami, Mohammad},
TITLE = {A node-capacitated {O}kamura-{S}eymour theorem},
JOURNAL = {Math. Program.},
FJOURNAL = {Mathematical Programming},
VOLUME = {153},
YEAR = {2015},
NUMBER = {2, Ser. A},
PAGES = {381--415},
}

[ abs | bib ]   Markov type and threshold embeddings, with J. Ding and Y. Peres (GAFA, 2013)

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.

@article {DLP13,
AUTHOR = {Ding, Jian and Lee, James R. and Peres, Yuval},
TITLE = {Markov type and threshold embeddings},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {23},
YEAR = {2013},
NUMBER = {4},
PAGES = {1207--1229},
}

[ abs | bib ]   On the 2-sum embedding conjecture, with D. E. Poore (SoCG'13)

The $2$-sum embedding conjecture (Lee-Sidiropoulos, FOCS 2009) states that all the shortest-path metrics supported on a family of graphs $\mathcal F$ admit a uniformly bi-Lipschitz embedding into $L_1$ if and only if the same property holds for the closure of $\mathcal F$ under edge sums. The problem has an equivalent formulation in terms of multi-commodity flow/cut gaps and appears to be a fundamental step in resolving the well-studied question of which families of graphs admit an approximate multi-commodity max-flow/min-cut theorem.

The $2$-sum conjecture is known to be true when $\mathcal F = {K_3}$, where $K_n$ denotes the complete graph on $n$ vertices; this is equivalent to the seminal result of Gupta, Newman, Rabinovich, and Sinclair (Combinatorica, 2004) on embeddings of series-parallel graphs into $L_1$. For $\mathcal F = {K_4}$, the conjecture was confirmed by Chakrabarti, Jaffe, Lee, and Vincent (FOCS 2008). In the present paper, we prove the conjecture holds for any finite family of graphs $\mathcal F$. In fact, we obtain a quantitatively optimal result: Any path metric on a graph formed by $2$-sums of arbitrarily many copies of $K_n$ embeds into $L_1$ with distortion $O(\log n)$. This is a consequence of a more general theorem that characterizes the $L_1$ distortion of the 2-sum closure of any family $\mathcal F$ in terms of constrained embeddings of the members of $\mathcal F$.

@inproceedings{LeePoore13,
author    = {James R. Lee and
Daniel E. Poore},
title     = {On the 2-sum embedding conjecture},
booktitle = {Symposuim on Computational Geometry 2013, SoCG '13, Rio de Janeiro,
Brazil, June 17-20, 2013},
pages     = {197--206},
year      = {2013},
}

[ abs | ]   A note on mixing times of planar random walks, with T. Qin (unpublished, 2012)
We present an infinite family of finite planar graphs $\{X_n\}$ with degree at most five and such that for some constant $c > 0$, $$\lambda_1(X_n) \geq c\left(\frac{\log \mathrm{diam}(X_n)}{\mathrm{diam}(X_n)}\right)^2\,,$$ where $\lambda_1$ denotes the smallest non-zero eigenvalue of the graph Laplacian. This significantly simplifies a construction of Louder and Souto. We also remark that such a lower bound cannot hold when the diameter is replaced by the average squared distance: There exists a constant $c > 0$ such that for any family $\{X_n\}$ of planar graphs we have $$\lambda_1(X_n) \leq c \left(\frac{1}{|X_n|^2} \sum_{x,y \in X_n} d(x,y)^2\right)^{-1}\,,$$ where $d$ denotes the path metric on $X_n$.
[ abs | bib ]   On the Hausdorff dimension of ultrametric subsets in $\mathbb{R}^n$, with M. Mendel and M. Moharrami (Fund. Math., 2012)

For every $\varepsilon > 0$, any subset of $\mathbb{R}^n$ with Hausdorff dimension larger than $(1-\varepsilon) n$ must have ultrametric distortion larger than $1/(4\varepsilon)$.

@article {LMM12,
AUTHOR = {Lee, James R. and Mendel, Manor and Moharrami, Mohammad},
TITLE = {On the {H}ausdorff dimension of ultrametric subsets in {$\Bbb R^n$}},
JOURNAL = {Fund. Math.},
FJOURNAL = {Fundamenta Mathematicae},
VOLUME = {218},
YEAR = {2012},
NUMBER = {3},
PAGES = {285--290},
}

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

@article{LOT14,
AUTHOR = {Lee, James R. and Gharan, Shayan Oveis and Trevisan, Luca},
FJOURNAL = {Journal of the ACM},
JOURNAL = {J. ACM},
NUMBER = {6},
PAGES = {Art. 37, 30},
TITLE = {Multiway spectral partitioning and higher-order {C}heeger
inequalities},
VOLUME = {61},
YEAR = {2014}
}

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

We show that every $n$-point tree metric admits a $(1+\varepsilon)$-bi-Lipschitz embedding into a $C(\varepsilon) \log n$-dimensional $\ell_1$ space for every $\varepsilon > 0$, where $C(\varepsilon) \leq O((1/\varepsilon)^4 \log (1/\varepsilon))$. This matches the natural volume lower bound up to a factor depending only on $\varepsilon$. Previously this was unknown even for complete binary trees.

@article {LLM13,
AUTHOR = {Lee, James R. and de Mesmay, Arnaud and Moharrami, Mohammad},
TITLE = {Dimension reduction for finite trees in {$\ell_1$}},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal
of Mathematics and Computer Science},
VOLUME = {50},
YEAR = {2013},
NUMBER = {4},
PAGES = {977--1032},
}

[ abs | ]   Expanders from the action of GL(2,Z) (unpublished, 2011)

(Mostly) expository note on Margulis-style expanders and their analysis. Significantly simpler than some previous analyses.

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

@article{DLP12,
AUTHOR = {Ding, Jian and Lee, James R. and Peres, Yuval},
FJOURNAL = {Annals of Mathematics. Second Series},
JOURNAL = {Ann. of Math. (2)},
NUMBER = {3},
PAGES = {1409--1471},
TITLE = {Cover times, blanket times, and majorizing measures},
VOLUME = {175},
YEAR = {2012}
}

[ abs | bib ]   Near-optimal bounds for embedding doubling spaces into $L_1$, with A. Sidiropoulos (STOC'11)

We show that there is a family of $n$-point uniformly doubling metrics that require bilipschitz distortion $\Omega\left(\sqrt{\frac{\log n}{\log \log n}}\right)$ under any embedding into $L_1$, matching the known upper bound to within an $O(\sqrt{\log \log n})$ factor.

@inproceedings{DBLP:conf/stoc/LeeS11,
author    = {James R. Lee and
Anastasios Sidiropoulos},
title     = {Near-optimal distortion bounds for embedding doubling spaces into
L${}_{\mbox{1}}$},
booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC}
2011, San Jose, CA, USA, 6-8 June 2011},
pages     = {765--772},
year      = {2011},
}

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

We prove diffusive lower bounds on the rate of escape of the random walk on infinite transitive graphs. Similar estimates hold for finite graphs, up to the relaxation time of the walk. Our approach uses nonconstant equivariant harmonic mappings taking values in a Hilbert space. For the special case of discrete, amenable groups, we present a more explicit proof of the Mok-Korevaar-Schoen theorem on the existence of such harmonic maps by constructing them from the heat flow on a Folner set.

@article {LP13,
AUTHOR = {Lee, James R. and Peres, Yuval},
TITLE = {Harmonic maps on amenable groups and a diffusive lower bound
for random walks},
JOURNAL = {Ann. Probab.},
FJOURNAL = {The Annals of Probability},
VOLUME = {41},
YEAR = {2013},
NUMBER = {5},
PAGES = {3392--3419},
}

[ abs | bib ]   Bilipschitz snowflakes and metrics of negative type, with M. Moharrami (STOC'10)

We show there exists a metric space $(X,d)$ such that $(X,\sqrt{d})$ admits a bilipschitz embedding into $L_2$, but $(X,d)$ does not admit an equivalent metric of negative type. In fact, we exhibit a strong quantitative bound: There are $n$-point subsets $Y_n \subseteq X$ such that any mapping of $(Y_n,d)$ to a metric of negative type incurs distortion at least $\tilde{\Omega}(\log n)^{1/4}$.

This answers an open question about the strength of strong vs. weak triangle inequalities in a number of semidefinite programs. Our construction sheds light on the power of various notions of “dual flows” that arise in algorithms for approximating the Sparsest Cut problem. It also has other interesting implications for bilipschitz embeddings of finite metric spaces.

@inproceedings{LMstoc10,
author    = {James R. Lee and
editor    = {Leonard J. Schulman},
title     = {Bilipschitz snowflakes and metrics of negative type},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages     = {621--630},
publisher = {{ACM}},
year      = {2010},
}

[ abs | bib ]   Pathwidth, trees, and random embeddings, with A. Sidiropoulos (Combinatorica 2013)

We show that every graph of pathwidth $k$ embeds into a distribution over random trees with distortion $c(k)$. In particular, this implies that whenever a non-trivial minor-closed family $\mathcal{F}$ of graphs does not contain all trees, the multi-commodity max-flow/min-cut gap is uniformly bounded for all instances over $\mathcal{F}$.

@article{LS13,
AUTHOR = {Lee, James R. and Sidiropoulos, Anastasios},
FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the
Theory of Computing},
JOURNAL = {Combinatorica},
NUMBER = {3},
PAGES = {349--374},
TITLE = {Pathwidth, trees, and random embeddings},
VOLUME = {33},
YEAR = {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.

@article {JLM11,
AUTHOR = {Jaffe, Alexander and Lee, James R. and Moharrami, Mohammad},
TITLE = {On the optimality of gluing over scales},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal
of Mathematics and Computer Science},
VOLUME = {46},
YEAR = {2011},
NUMBER = {2},
PAGES = {270--282},
}

[ abs | bib ]   Genus and the geometry of the cut graph, with A. Sidiropoulos (SODA'10)

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.

@inproceedings{DBLP:conf/soda/LeeS10,
author    = {James R. Lee and
Anastasios Sidiropoulos},
title     = {Genus and the Geometry of the Cut Graph},
booktitle = {Proceedings of the Twenty-First Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2010, Austin, Texas, USA, January 17-19, 2010},
pages     = {193--201},
year      = {2010},
}

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

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

@article{BLS10,
AUTHOR = {Borradaile, Glencora and Lee, James R. and Sidiropoulos,
Anastasios},
FJOURNAL = {Computational Geometry. Theory and Applications},
JOURNAL = {Comput. Geom.},
NUMBER = {8},
PAGES = {655--662},
TITLE = {Randomly removing {$g$} handles at once},
VOLUME = {43},
YEAR = {2010}
}

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

@article {KLPT11,
AUTHOR = {Kelner, Jonathan A. and Lee, James R. and Price, Gregory N.
and Teng, Shang-Hua},
TITLE = {Metric uniformization and spectral bounds for graphs},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {21},
YEAR = {2011},
NUMBER = {5},
PAGES = {1117--1143},
}

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

@article {MR2665882,
AUTHOR = {Biswal, Punyashloka and Lee, James R. and Rao, Satish},
TITLE = {Eigenvalue bounds, spectral partitioning, and metrical
deformations via flows},
JOURNAL = {J. ACM},
FJOURNAL = {Journal of the ACM},
VOLUME = {57},
YEAR = {2010},
NUMBER = {3},
PAGES = {Art. 13, 23},
}

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

@article {DLL11,
AUTHOR = {Dekel, Yael and Lee, James R. and Linial, Nathan},
TITLE = {Eigenvectors of random graphs: nodal domains},
JOURNAL = {Random Structures Algorithms},
FJOURNAL = {Random Structures \& Algorithms},
VOLUME = {39},
YEAR = {2011},
NUMBER = {1},
PAGES = {39--58},
}

[ abs | ]   Eigenvalue multiplicity and volume growth, with Y. Makarychev (unpublished, 2008)

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)

We establish that the multi-commodity max-flow/min-cut gap for series-parallel graphs is at least $2$. Our approach uses the coarse differentiation methodology of Eskin, Fisher, and Whyte.

@article {LR10,
AUTHOR = {Lee, James R. and Raghavendra, Prasad},
TITLE = {Coarse differentiation and multi-flows in planar graphs},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal
of Mathematics and Computer Science},
VOLUME = {43},
YEAR = {2010},
NUMBER = {2},
PAGES = {346--362},
}

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

@article {GLR10,
AUTHOR = {Guruswami, Venkatesan and Lee, James R. and Razborov,
Alexander},
TITLE = {Almost {E}uclidean subspaces of {$\ell^N_1$} via expander
codes},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal on Combinatorics and
the Theory of Computing},
VOLUME = {30},
YEAR = {2010},
NUMBER = {1},
PAGES = {47--68},
}

[ abs | bib ]   Trees and Markov convexity, with A. Naor and Y. Peres (SODA'06; GAFA)

We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion. We also introduce a new metric invariant called Markov convexity, and show how it can be used to compute the Euclidean distortion of any metric tree up to universal factors.

@article{LNP09,
AUTHOR = {Lee, James R. and Naor, Assaf and Peres, Yuval},
FJOURNAL = {Geometric and Functional Analysis},
JOURNAL = {Geom. Funct. Anal.},
NUMBER = {5},
PAGES = {1609--1659},
TITLE = {Trees and {M}arkov convexity},
VOLUME = {18},
YEAR = {2009}
}

[ abs | bib ]   Vertex cuts, random walks, and dimension reduction in series-parallel graphs, with B. Brinkman and A. Karagiozova (STOC'07)

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.

@inproceedings{DBLP:conf/stoc/BrinkmanKL07,
AUTHOR = {Bo Brinkman and Adriana Karagiozova and James R. Lee},
BOOKTITLE = {Proceedings of the 39th Annual {ACM} Symposium on Theory of
Computing, San Diego, California, USA, June 11-13,
2007},
DOI = {10.1145/1250790.1250882},
PAGES = {621--630},
TITLE = {Vertex cuts, random walks, and dimension reduction in series-
parallel graphs},
YEAR = {2007}
}

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

@inproceedings{DBLP:conf/approx/GuruswamiLW08,
author    = {Venkatesan Guruswami and
James R. Lee and
Avi Wigderson},
title     = {Euclidean Sections of with Sublinear Randomness and Error-Correction
over the Reals},
booktitle = {Approximation, Randomization and Combinatorial Optimization. Algorithms
and Techniques, 11th International Workshop, {APPROX} 2008, and 12th
International Workshop, {RANDOM} 2008, Boston, MA, USA, August 25-27,
2008. Proceedings},
pages     = {444--454},
year      = {2008},
}

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

@inproceedings{LN06,
author    = {James R. Lee and
Assaf Naor},
title     = {Lp metrics on the Heisenberg group and the Goemans-Linial conjecture},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages     = {99--108},
year      = {2006},
}

[ abs | bib ]   Volume distortion for subsets of Euclidean spaces (SoCG'06, DCG)

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

@article{LeeVolume09,
AUTHOR = {Lee, James R.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of
Mathematics and Computer Science},
JOURNAL = {Discrete Comput. Geom.},
NUMBER = {4},
PAGES = {590--615},
TITLE = {Volume distortion for subsets of {E}uclidean spaces},
VOLUME = {41},
YEAR = {2009}
}

[ abs | bib ]   Algorithms on negatively curved spaces, with R. Krauthgamer (FOCS'06)

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.

@inproceedings{KL06,
author    = {Robert Krauthgamer and
James R. Lee},
title     = {Algorithms on negatively curved spaces},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages     = {119--132},
year      = {2006},
}

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

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

@article {FL07,
AUTHOR = {Feige, Uriel and Lee, James R.},
TITLE = {An improved approximation ratio for the minimum linear
arrangement problem},
JOURNAL = {Inform. Process. Lett.},
FJOURNAL = {Information Processing Letters},
VOLUME = {101},
YEAR = {2007},
NUMBER = {1},
PAGES = {26--29},
}

[ abs | bib ]   Fréchet embeddings of negative type metrics, with S. Arora and A. Naor (DCG 2007)

This paper strengthens the main result of Euclidean distortion and the Sparsest Cut by showing that one can use a Fréchet embedding.

@article {ALN07,
AUTHOR = {Arora, Sanjeev and Lee, James R. and Naor, Assaf},
TITLE = {Fr\'echet embeddings of negative type metrics},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal
of Mathematics and Computer Science},
VOLUME = {38},
YEAR = {2007},
NUMBER = {4},
PAGES = {726--739},
}

[ abs | bib ]   Euclidean distortion and the Sparsest Cut, with S. Arora and A. Naor (STOC'05; JAMS)

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

@article {LN08,
AUTHOR = {Arora, Sanjeev and Lee, James R. and Naor, Assaf},
TITLE = {Euclidean distortion and the sparsest cut},
JOURNAL = {J. Amer. Math. Soc.},
FJOURNAL = {Journal of the American Mathematical Society},
VOLUME = {21},
YEAR = {2008},
NUMBER = {1},
PAGES = {1--21},
}

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

@article {FHL08,
AUTHOR = {Feige, Uriel and Hajiaghayi, Mohammadtaghi and Lee, James R.},
TITLE = {Improved approximation algorithms for minimum weight vertex
separators},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = {SIAM Journal on Computing},
VOLUME = {38},
YEAR = {2008},
NUMBER = {2},
PAGES = {629--657},
}


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

@inproceedings{DBLP:conf/soda/Lee05,
AUTHOR = {James R. Lee},
BOOKTITLE = {Proceedings of the Sixteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2005, Vancouver, British
PAGES = {92--101},
TITLE = {On distance scales, embeddings, and efficient relaxations of the cut
cone},
YEAR = {2005}
}

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

We present some new observations concerning the relation of finite subsets of $L_1$ to dimension reduction, topology, and Euclidean distortion.

@article {LMM05,
AUTHOR = {Lee, James R. and Mendel, Manor and Naor, Assaf},
TITLE = {Metric structures in {$L_1$}: dimension, snowflakes, and
average distortion},
JOURNAL = {European J. Combin.},
FJOURNAL = {European Journal of Combinatorics},
VOLUME = {26},
YEAR = {2005},
NUMBER = {8},
PAGES = {1180--1190},
}

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

We develop here a new multi-scale embedding method that we term measured descent and use it to resolve a number of open questions in the theory of embeddings of finite metric spaces.

@article {KLMN05,
AUTHOR = {Krauthgamer, R. and Lee, J. R. and Mendel, M. and Naor, A.},
TITLE = {Measured descent: a new embedding method for finite metrics},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {15},
YEAR = {2005},
NUMBER = {4},
PAGES = {839--858},
}

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

@article {LN05,
AUTHOR = {Lee, James R. and Naor, Assaf},
TITLE = {Extending {L}ipschitz functions via random metric partitions},
JOURNAL = {Invent. Math.},
FJOURNAL = {Inventiones Mathematicae},
VOLUME = {160},
YEAR = {2005},
NUMBER = {1},
PAGES = {59--95},
}

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

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.

@article {KL05,
AUTHOR = {Krauthgamer, Robert and Lee, James R.},
TITLE = {The black-box complexity of nearest-neighbor search},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {348},
YEAR = {2005},
NUMBER = {2-3},
PAGES = {262--276},
}

[ abs | bib ]   Absolute Lipschitz extendability, with A. Naor (CRAS, 2004)
@article{LNLip04,
AUTHOR = {Lee, James R. and Naor, Assaf},
FJOURNAL = {Comptes Rendus Math\'ematique. Acad\'emie des Sciences. Paris},
JOURNAL = {C. R. Math. Acad. Sci. Paris},
NUMBER = {11},
PAGES = {859--862},
TITLE = {Absolute {L}ipschitz extendability},
VOLUME = {338},
YEAR = {2004}
}

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

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.

@inproceedings {KL04soda,
AUTHOR = {Krauthgamer, Robert and Lee, James R.},
TITLE = {Navigating nets: simple algorithms for proximity search},
BOOKTITLE = {Proceedings of the {F}ifteenth {A}nnual {ACM}-{SIAM}
{S}ymposium on {D}iscrete {A}lgorithms},
PAGES = {798--807},
PUBLISHER = {ACM, New York},
YEAR = {2004},
MRCLASS = {68P05},
MRNUMBER = {2290969},
}

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

We show that every embedding of the level $k$ diamond graph of Newman and Rabinovich into $L_p$ with $1 < p \leq 2$ requires distortion at least $\sqrt{k(p-1)+1}$. An immediate corollary is that there exist arbitrary large $n$-point subsets $X \subseteq L_1$ such that any $D$-embedding of $X$ into $\ell_1^d$ requires $d \geq n^{\Omega(1/D^2)}$. This gives a simple proof of the $L_1$ dimension reduction lower bound of Brinkman and Charikar.

@article {LNdiamond04,
AUTHOR = {Lee, J. R. and Naor, A.},
TITLE = {Embedding the diamond graph in {$L_p$} and dimension reduction
in {$L_1$}},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {14},
YEAR = {2004},
NUMBER = {4},
PAGES = {745--747},
}

[ abs | bib ]   Bounded geometries, fractals, and low-distortion embeddings, with A. Gupta and R. Krauthgamer (FOCS'03)

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

@inproceedings {GKL03,
author    = {Anupam Gupta and
Robert Krauthgamer and
James R. Lee},
title     = {Bounded Geometries, Fractals, and Low-Distortion Embeddings},
booktitle = {44th Symposium on Foundations of Computer Science {(FOCS} 2003), 11-14
October 2003, Cambridge, MA, USA, Proceedings},
pages     = {534--543},
year      = {2003},
doi       = {10.1109/SFCS.2003.1238226},
}

[ abs | bib ]   The intrinsic dimensionality of graphs, with R. Krauthgamer (STOC'03; Combinatorica)

We resolve a conjecture of Levin together with Linial, London, and Rabinovich about embeddings of graphs whose intrinsic metric has polynomial growth. We also resolve positively a related embedding question of Benjamini and Schramm.

@article {KL07,
AUTHOR = {Krauthgamer, Robert and Lee, James R.},
TITLE = {The intrinsic dimensionality of graphs},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal on Combinatorics and
the Theory of Computing},
VOLUME = {27},
YEAR = {2007},
NUMBER = {5},
PAGES = {551--585},
}

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

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.

@article {KKL04,
AUTHOR = {Kortsarz, Guy and Krauthgamer, Robert and Lee, James R.},
TITLE = {Hardness of approximation for vertex-connectivity network
design problems},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = {SIAM Journal on Computing},
VOLUME = {33},
YEAR = {2004},
NUMBER = {3},
PAGES = {704--720},
}