James R. Lee

James R. Lee

Computer Science
University of Washington

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


Recent papers are on the arxiv


Winter 2018: Theory of computation
Winter 2017: Applied algorithms
Randomized algorithms [AU'16, WI 15]
Spring 2016: Computability and complexity theory
Winter 2016: Entropy optimality
Foundations of Computing I [AU'15, SP'15]

Students: Jeffrey Hon, Austrin Stromme

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.

Talks and events:   [earlier | later]

Recent works:   [ click on authors for abstract; expand / collapse all ]

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

  • 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 A)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most A.

  • If (G, x) is the distributional limit of finite graphs that can be sphere-packed in Rd, then the conformal growth exponent of (G, x) 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.

  • For a unimodular random graph (G, x), 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, x), 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).

  • A region intersection graph over a base graph G0 is a graph G whose vertices correspond to connected subsets of G0 with an edge between two vertices if the corresponding regions intersect. We show that if G0 excludes the complete graph Kh as a minor, then every region intersection graph over G0 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).

  • Geometric and Functional Analysis (GAFA), 2017.

    We show that if (G, x) 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 Zd. 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.

  • To appear, Journey Through Discrete Mathematics. A Tribute to Jiri Matousek, 2016.

    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 W1 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 the entropic interpolation approach suggests a natural attack on the MLSI conjecture.

  • SIAM Journal on Discrete Math, 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.

Some older selected papers:   [ click on authors for abstract; expand / collapse all ]

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