Professor
Computer Science
University of Washington
Paul G. Allen Center, Room 640
jrl [at] cs [dot] washington [dot] edu
Associate Editor, SIDMA.
Associate Editor, SICOMP.
I will be on the PC for STOC 2017.
Recent PCs: SODA 2014, ICALP 2014,
FOCS 2014.
Research interests:
Algorithms, complexity, the theory of computation. Geometry and analysis at the interface between the continuous and discrete. Probability and stochastic processes.
Students: Jeffrey Hon
Ben Eggers, Yuegi Sheng, Austrin Stromme
Recent works: [ click on authors for abstract; expand / collapse all ]
A region intersection graph over a base graph G_{0} is a graph G whose vertices correspond to connected subsets of G_{0} with an edge between two vertices if the corresponding regions intersect. We show that if G_{0} excludes the complete graph K_{h} as a minor, then every region intersection graph over G_{0} with m edges has a balanced separator with O(sqrt{m}) nodes. If G has uniformly bounded vertex degrees, we show the separator is found by spectral partitioning.
A string graph is the intersection graph of continuous arcs in the plane. The preceding result implies that every string graph with m edges has a balanced separator of size O(sqrt{m}). This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010) and improves over the O(sqrt{m} log m) bound of Matousek (2013).
We 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 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.
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 the entropic interpolation approach suggests a natural attack on the MLSI conjecture.
Chang's Lemma is a widely employed result in additive combinatorics. It gives optimal bounds on the dimension of the large spectrum of probability distributions on finite abelian groups. In this note, we show how Chang's Lemma and a powerful variant due to Bloom both follow easily from an approximation theorem for probability measures in terms of generalized Riesz products. The latter result involves no algebraic structure. The proofs are correspondingly elementary.
[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.
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)
[ PPT slides ]
Some older selected papers: [ click on authors for abstract; expand / collapse all ]
[credit: Fiorini, Rothvoss, and Tiwary]
We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.
Video: Linear programming and constraint satisfaction (Simons Institute)
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 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.
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.
Journal of the ACM, 57(3): 13(1-23), 2010.
47th Annual IEEE Symposium on Foundations of Computer Science, pgs. 99-108, 2006.
Journal of the American Mathematical Society, 21(1): 1-21, 2008.
SIAM Journal on Computing, 38(2): 629-657, 2008.
@article {LeeNaor05, 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}, ISSN = {0020-9910}, }
Combinatorica, 27(5): 551-585, 2007.
My research has been generously supported by the National Science Foundation, the Sloan Foundation, Microsoft, and the Simons Institute.