Associate Professor
Computer Science
University of Washington
Paul G. Allen Center, Room 640
jrl [at] cs [dot] washington [dot] edu
Computer Science & Engineering
University of Washington
AC 101, Box 352350
Seattle, WA 98195
Melody Kadenko
melody [at] cs [dot] washington [dot] edu
Research interests:
Algorithms and complexity theory. Geometry and analysis at the interface between the continuous and discrete. Probability, spectral graph theory, and metric geometry.
I recently organized the Simons Institue program on Algorithmic Spectral Graph Theory. See my open lecture for a taste, or start with the boot camp.
I was on the program committees for SODA 2014, ICALP 2014, and FOCS 2014.
Winter 2015: Randomized algorithms
Current students: Mert Salgam, Jeffrey Man Hin Hon
Current postdocs: Ronen Eldan
Selected recent papers and preprints: [ click on authors for abstract; expand / collapse all ]
[credit: convex algebraic geometry wiki]
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.
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 (Institute for Advanced Study)
We give smal-ball estimates which show that general discrete-time martingales taking values in a Euclidean space must escape from the origin at least as fast as a standard one-dimensional random walk with the same conditional variances. We make the necessary assumptions that the jumps are bounded, and the conditional variances are deterministic. Without the latter assumption, counterintuitive behaviors can develop, as was suggested in the 1960s by certain solutions to PDE arising in nonlinear filtration.
This has applications to small-ball estimates for random walks on vertex-transitive graphs (e.g., Cayley graphs). We show that for every infinite, connected, vertex-transitive graph with bounded degrees, the probability for the random walk to be within eps*sqrt{T} of its starting point after T steps is O(eps).
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. 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. 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. Our arguments yield an alternate proof of Li and Winter's recent strengthening of strong subadditivity for quantum relative entropy.
[credit: Fiorini, Rothvoss, and Tiwary]
[Updated 18-Feb-2015]
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)
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.
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.
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. This suggests some non-linear analogs of Kwapien's theorem. For instance, a subset of L^1 threshold-embeds into Hilbert space if and only if it has Markov type 2.
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.
Some older selected papers: [ click on authors for abstract; expand / collapse all ]
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.
Geometric and Functional Analysis (GAFA), 15(4): 839-858, 2005.
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.