Source author record

James R. Lee

James R. Lee appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.MG math.PR Data Structures and Algorithms math.CO Computational Complexity Discrete Mathematics math.OC Computational Geometry Information Theory math.DG math.FA math.IT math.SP quant-ph

Catalog footprint

What is connected

22works

14topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements

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.

preprint2020arXiv

Conformal growth rates and spectral geometry on distributional limits of graphs

For a unimodular random graph $(G,ρ)$, 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,ρ)$, which is the best asymptotic degree of volume growth of balls that can be achieved by such a reweighting. 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. This has interesting consequences for many low-dimensional models. The consequences in dimension two are particularly strong. It establishes that models like the uniform infinite planar triangulation (UIPT) and quadrangulation (UIPQ) almost surely have spectral dimension at most two. It also establishes a conjecture of Benjamini and Schramm (2001) by extending their Recurrence Theorem from planar graphs to arbitrary families of $H$-minor free graphs. More generally, it strengthens the work of Gurel-Gurevich and Nachmias (2013) who established recurrence for distributional limits of planar graphs when the degree of the root has exponential tails. We further present a general method for proving subdiffusivity of the random walk on a large class of models, including UIPT and UIPQ, using only the volume growth profile of balls in the intrinsic metric.

preprint2020arXiv

Pure entropic regularization for metrical task systems

We show that on every $n$-point HST metric, 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 by Bubeck et al. (SODA 2019), 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 can be viewed as 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.

preprint2016arXiv

Approximate Constraint Satisfaction Requires Large LP Relaxations

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.

preprint2016arXiv

Covering the large spectrum and generalized Riesz products

Chang's Lemma is a widely employed result in additive combinatorics. It gives bounds on the dimension of the large spectrum of probability distributions on finite abelian groups. Recently, Bloom (2016) presented a powerful variant of Chang's Lemma that yields the strongest known quantitative version of Roth's theorem on 3-term arithmetic progressions in dense subsets of the integers. In this note, we show how such theorems can be derived from the approximation of probability measures via entropy maximization.

preprint2016arXiv

Diffusive estimates for random walks on stationary random graphs of polynomial growth

Let $(G,ρ)$ be a stationary random graph, and use $B^G_ρ(r)$ to denote the ball of radius $r$ about $ρ$ in $G$. Suppose that $(G,ρ)$ has annealed polynomial growth, in the sense that $\mathbb{E}[|B^G_ρ(r)|] \leq O(r^k)$ for some $k > 0$ and every $r \geq 1$. Then there is an infinite sequence of times $\{t_n\}$ at which the random walk $\{X_t\}$ on $(G,ρ)$ is at most diffusive: Almost surely (over the choice of $(G,ρ)$), there is a number $C > 0$ such that \[ \mathbb{E} \left[\mathrm{dist}_G(X_0, X_{t_n})^2 \mid X_0 = ρ, (G,ρ)\right]\leq C t_n\qquad \forall n \geq 1\,. \] 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 (2015), 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 $\{t_n\}$ is necessary, as there are stationary random graphs of (almost sure) polynomial growth where the random walk is almost surely superdiffusive at an infinite subset of times.

preprint2016arXiv

Transport-entropy inequalities and curvature in discrete-space Markov chains

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.

preprint2015arXiv

A Gaussian upper bound for martingale small-ball probabilities

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)}\,.\] Following [Lee-Peres, Ann. Probab. 2013], this has applications to diffusive estimates for random walks on vertex-transitive graphs.

preprint2014arXiv

Lower bounds on the size of semidefinite programming relaxations

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.

preprint2014arXiv

Multi-way spectral partitioning and higher-order Cheeger inequalities

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 an approximate 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, i.e., 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. 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 tradeoff between the expansion of sets of size $\approx n/k$, and the $k$th smallest eigenvalue of the normalized Laplacian matrix, denoted $λ_k$. In particular, we show that in every graph there is a set of size at most $2n/k$ which has expansion at most $O(\sqrt{λ_k \log k})$. This bound is tight, up to constant factors, for the "noisy hypercube" graphs.

preprint2013arXiv

A lower bound on dimension reduction for trees in \ell_1

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

preprint2013arXiv

Harmonic maps on amenable groups and a diffusive lower bound for random walks

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 Følner set.

preprint2013arXiv

Markov type and threshold embeddings

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 $f_τ : X \to Y : τ> 0 \}$ such that for every $x,y \in X$, \[ d_X(x,y) \geq τ=> d_Y(f_τ(x),f_τ(y)) \geq \|φ_τ\|_{\Lip} τ/K \] where $\|f_τ\|_{\Lip}$ denotes the Lipschitz constant of $f_τ$. 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 $X \subseteq L_1$ threshold-embeds into Hilbert space if and only if X has Markov type 2.

preprint2012arXiv

A node-capacitated Okamura-Seymour theorem

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.

preprint2012arXiv

A note on mixing times of planar random walks

We present an infinite family of finite planar graphs $\{X_n\}$ with degree at most five and such that for some constant $c > 0$, $$ λ_1(X_n) \geq c(\frac{\log \diam(X_n)}{\diam(X_n)})^2\,, $$ where $λ_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 $$ λ_1(X_n) \leq c (\frac{1}{|X_n|^2} \sum_{x,y \in X_n} d(x,y)^2)^{-1}\,, $$ where $d$ denotes the path metric on $X_n$.

preprint2012arXiv

On the Hausdorff dimension of ultrametric subsets in R^n

For every e>0, any subset of R^n with Hausdorff dimension larger than (1-e)n must have ultrametric distortion larger than 1/(4e).

preprint2012arXiv

Pathwidth, trees, and random embeddings

We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair states that for every minor-closed family of graphs $F$, there is a constant $c(F)$ such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from $F$ is at most $c(F)$. The preceding embedding theorem is used to prove this conjecture whenever the family $F$ does not contain all trees.

preprint2011arXiv

Cover times, blanket times, and majorizing measures

We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph $G$ is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on $G$, scaled by the number of edges in $G$. This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was $O((\log \log n)^2)$ for $n$-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).

preprint2011arXiv

Dimension reduction for finite trees in L_1

We show that every n-point tree metric admits a (1+eps)-embedding into a C(eps) log n-dimensional L_1 space, for every eps > 0, where C(eps) = O((1/eps)^4 log(1/eps)). This matches the natural volume lower bound up to a factor depending only on eps. Previously, it was unknown whether even complete binary trees on n nodes could be embedded in O(log n) dimensions with O(1) distortion. For complete d-ary trees, our construction achieves C(eps) = O(1/eps^2).

preprint2011arXiv

Metric uniformization and spectral bounds for graphs

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. In particular, 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.

preprint2011arXiv

On the optimality of gluing over scales

We show that for every $α> 0$, there exist $n$-point metric spaces (X,d) where every "scale" admits a Euclidean embedding with distortion at most $α$, but the whole space requires distortion at least $Ω(\sqrt{α\log n})$. This shows that the scale-gluing lemma [Lee, SODA 2005] is tight, and disproves a conjecture stated there. This matching upper bound was known to be tight at both endpoints, i.e. when $α= Θ(1)$ and $α= Θ(\log n)$, but nowhere in between. More specifically, we exhibit $n$-point spaces with doubling constant $λ$ requiring Euclidean distortion $Ω(\sqrt{\log λ\log n})$, which also shows that the technique of "measured descent" [Krauthgamer, et. al., Geometric and Functional Analysis] is optimal. We extend this to obtain a similar tight result for $L_p$ spaces with $p > 1$.

preprint2010arXiv

Randomly removing g handles at once

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 $2^{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).

James R. Lee

What is connected

Connect this record

See the researcher in context

Building this map preview

22 published item(s)

Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements

Conformal growth rates and spectral geometry on distributional limits of graphs

Pure entropic regularization for metrical task systems

Approximate Constraint Satisfaction Requires Large LP Relaxations

Covering the large spectrum and generalized Riesz products

Diffusive estimates for random walks on stationary random graphs of polynomial growth

Transport-entropy inequalities and curvature in discrete-space Markov chains

A Gaussian upper bound for martingale small-ball probabilities

Lower bounds on the size of semidefinite programming relaxations

Multi-way spectral partitioning and higher-order Cheeger inequalities

A lower bound on dimension reduction for trees in \ell_1

Harmonic maps on amenable groups and a diffusive lower bound for random walks

Markov type and threshold embeddings

A node-capacitated Okamura-Seymour theorem

A note on mixing times of planar random walks

On the Hausdorff dimension of ultrametric subsets in R^n

Pathwidth, trees, and random embeddings

Cover times, blanket times, and majorizing measures

Dimension reduction for finite trees in L_1

Metric uniformization and spectral bounds for graphs

On the optimality of gluing over scales

Randomly removing g handles at once