James R. Lee

Home   |   Publications   |   tcsmath   [old]

Computer Science
University of Washington

Paul G. Allen Center, Room 640
jrl [at] cs [dot] washington [dot] edu


Research interests:
Algorithms, complexity, and the theory of computation. Geometry and analysis at the interface between the continuous and discrete. Probability and stochastic processes. Metric embeddings, spectral graph theory, convex optimization.

James R. Lee

Recent work:

[ abs | ]   Fusible HSTs and the randomized k-server conjecture (preprint, 2017)

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 | ]   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 | ]   Discrete uniformizing metrics on distributional limits of sphere packings (To appear, GAFA)

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.

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

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.

@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 2017)

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

    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},

Other selected papers:

[ 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

  author    = {James R. Lee and
               Prasad Raghavendra and
               David Steurer},
  title     = {Lower Bounds on the Size of Semidefinite Programming
  booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on
               of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
  pages     = {567--576},
  year      = {2015},
  note      = {Full version at \verb|https://arxiv.org/abs/1411.6317|}
[ 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)

@article {ElDuke18,
    AUTHOR = {Eldan, Ronen and Lee, James R.},
     TITLE = {Regularization under diffusion and anticoncentration of the
              information content},
   JOURNAL = {Duke Math. J.},
  FJOURNAL = {Duke Mathematical Journal},
    VOLUME = {167},
      YEAR = {2018},
    NUMBER = {5},
     PAGES = {969--993},
[ 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}
   JOURNAL = {J. ACM},
  FJOURNAL = {Journal of the ACM},
    VOLUME = {63},
      YEAR = {2016},
    NUMBER = {4},
     PAGES = {Art. 34, 22},
[ 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},
     TITLE = {Multiway spectral partitioning and higher-order {C}heeger
   JOURNAL = {J. ACM},
  FJOURNAL = {Journal of the ACM},
    VOLUME = {61},
      YEAR = {2014},
    NUMBER = {6},
     PAGES = {Art. 37, 30},
[ 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},
     TITLE = {Cover times, blanket times, and majorizing measures},
   JOURNAL = {Ann. of Math. (2)},
  FJOURNAL = {Annals of Mathematics. Second Series},
    VOLUME = {175},
      YEAR = {2012},
    NUMBER = {3},
     PAGES = {1409--1471},
[ 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 ]   \(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.

  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 ]   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
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {38},
      YEAR = {2008},
    NUMBER = {2},
     PAGES = {629--657},

My research has been generously supported by the National Science Foundation, the Simons Foundation, the Sloan Foundation, and Microsoft.