If X = (𝖬_n(ℝ),‖⋅‖_X) is a unitarily invariant normed space, i.e., ‖𝖴𝖠𝖵‖_X = ‖𝖠‖_X for every matrix 𝖠 ∈ 𝖬_n(ℝ) and every two orthogonal matrices 𝖴,𝖵 ∈ 𝖬_n(ℝ), then we evaluate up to universal constant factors the smallest σ > 0 for which there is a probability distribution over partitions of X into clusters of diameter at most 1 yet for every two matrices 𝖠,𝖡 ∈ 𝖬_n(ℝ) the probability that they fall into distinct clusters is at most σ times the X-distance between 𝖠 and 𝖡. Specifically, we prove that this infimal σ, which is called the separation modulus of X and is denoted SEP(X), satisfies: (1) SEP(X) = Θ(√n⋅ ‖𝖨_n‖_X⋅ diam(B_X)), where 𝖨_n is the n-by-n identity matrix and diam(B_X) is the diameter with respect to the standard Euclidean metric on 𝖬_n(ℝ) of the unit ball B_ X of X. Our proof of (1) proceeds through an asymptotic evaluation of the spectral gap of the Laplacian with Dirichlet boundary conditions on B_ X, which we achieve by exact computations for a Jacobi orthogonal random matrix ensemble. Assuming oracle access to norm evaluations in X, by combining (1) with a new deterministic algorithm for a O(1)-approximation of the diameter of convex bodies in ℝⁿ that are given by a weak membership oracle and are symmetric with respect to coordinate permutations and reflections about the standard axes (this task is famously known to be impossible in the absence of such symmetries), we get an oracle polynomial time algorithm whose output is the separation modulus of X up to universal constant factors. Another example of a consequence of (1) is that for each m ∈ {1,…,n} the separation modulus of the m'th Ky Fan norm on 𝖬_n(ℝ) is bounded from above and from below by universal constant multiples of m√n if m ⩾ √n, and of n if m ⩽ √n. We also deduce from (1) an upper bound on the Lipschitz extension modulus of X that improves over the previously best-known bound even in the special case when X is 𝖬_n(ℝ) equipped with the 𝓁₂ⁿ → 𝓁₂ⁿ operator norm.

We design a deterministic algorithm that, given \(n\) points in a typical constant degree regular graph, queries \(O(n)\) distances to output a constant factor approximation to the average distance among those points, thus answering a question posed in [Mendel and Naor 2015]. Our algorithm uses the method of [Mendel and Naor 2015] to construct a sequence of constant degree graphs that are expanders with respect to certain nonpositively curved metric spaces, together with a new rigidity theorem for metric transforms of nonpositively curved metric spaces. The fact that our algorithm works for typical (uniformly random) constant degree regular graphs rather than for all constant degree graphs is unavoidable, thanks to the following impossibility result that we obtain: For every fixed \(k \in \mathbb N\), the approximation factor of any algorithm for average distance that works for all constant degree graphs and queries \(o(n^{1+1/k})\) distances must necessarily be at least \(2(k + 1)\). This matches the upper bound attained by the algorithm that was designed for general finite metric spaces in [Barhum et. al. 2007]. Thus, any algorithm for average distance in constant degree graphs whose approximation guarantee is less than 4 must query \(\Omega(n^2)\) distances, any such algorithm whose approximation guarantee is less than 6 must query \(\Omega(n^{3/2})\) distances, any such algorithm whose approximation guarantee less than 8 must query \(\Omega(n^{3/4})\) distances, and so forth, and furthermore there exist algorithms achieving those parameters.

We resolve multiple fundamental open questions about the bi-Lipschitz geometry of subsets of \(L_p\) for \(2 \le p \lt \infty\) via a novel multiscale and localization framework. Specifically, we prove that the separation modulus of any \(n\)-point subset of \(L_p\) is \(\Theta_p(\sqrt{\log n})\). If that subset has doubling constant \(\lambda\), then we obtain the improved bound \(O_p(\sqrt{\log \lambda})\), which is new even for the Euclidean space \(p = 2\). We also break the longstanding \(O(\log n)\) barrier for embedding every \(n\)-point subset of \(L_p\) into Euclidean space for all \(p \gt 2\), as well as the longstanding \(O((\log n)/\log\log n)\) barrier for their Lipschitz extension modulus.

We investigate the approximability of the following optimization problem. The input is an n× n matrix A=(Aij) with real entries and an origin-symmetric convex body K⊂ ℝn that is given by a membership oracle. The task is to compute (or approximate) the maximum of the quadratic form ∑i=1n∑j=1n Aij xixj=⟨ x,Ax⟩ as x ranges over K. This is a rich and expressive family of optimization problems; for different choices of matrices A and convex bodies K it includes a diverse range of optimization problems like max-cut, Grothendieck/non-commutative Grothendieck inequalities, small set expansion and more. While the literature studied these special cases using case-specific reasoning, here we develop a general methodology for treatment of the approximability and inapproximability aspects of these questions.

Let S1 (the Schatten–von Neumann trace class) denote the Banach space of all compact linear operators T : ℓ2 → ℓ2 whose nuclear norm ||T||S1 = Σj=1∞ σj(T) is finite, where {σj(T)}j=1∞ are the singular values of T. We prove that for arbitrarily large n ∊ ℕ there exists a subset with that cannot be embedded with bi-Lipschitz distortion O(1) into any no(1)-dimensional linear subspace of S1. is not even a O(1)-Lipschitz quotient of any subset of any no(1)-dimensional linear subspace of S1. Thus, S1 does not admit a dimension reduction result á la Johnson and Lindenstrauss (1984), which complements the work of Harrow, Montanaro and Short (2011) on the limitations of quantum dimension reduction under the assumption that the embedding into low dimensions is a quantum channel. Such a statement was previously known with S1 replaced by the Banach space ℓ1 of absolutely summable sequences via the work of Brinkman and Charikar (2003). In fact, the above set can be taken to be the same set as the one that Brinkman and Charikar considered, viewed as a collection of diagonal matrices in S1. The challenge is to demonstrate that cannot be faithfully realized in an arbitrary low-dimensional subspace of S1, while Brinkman and Charikar obtained such an assertion only for subspaces of S1 that consist of diagonal operators (i.e., subspaces of ℓ1). We establish this by proving that the Markov 2-convexity constant of any finite dimensional linear subspace X of S1 is at most a universal constant multiple of .

Andoni, Krauthgamer and Razenshteyn (AKR) proved (STOC’15) that a finite-dimensional normed space (X, ‖·‖x) admits a O(1) sketching algorithm (namely, with O(1) sketch size and O(1) approximation) if and only if for every ε ∊ (0, 1) there exist α  1 and an embedding f : X → ℓ1–ε such that ‖x – y‖x  ‖f(x) – f(y)‖1–ε  α‖x – y‖x for all x, y ∊ X. The “if part” of this theorem follows from a sketching algorithm of Indyk (FOCS 2000). The contribution of AKR is therefore to demonstrate that the mere availability of a sketching algorithm implies the existence of the aforementioned geometric realization. Indyk's algorithm shows that the “if part” of the AKR characterization holds true for any metric space whatsoever, i.e., the existence of an embedding as above implies sketchability even when X is not a normed space. Due to this, a natural question that AKR posed was whether the assumption that the underlying space is a normed space is needed for their characterization of sketchability. We resolve this question by proving that for arbitrarily large n ∊ ℕ there is an n-point metric space (M(n), dM(n)) which is O(1)-sketchable yet for every ε ∊ (0, ψ), if α(n)  1 and fn : M(n) → ℓ1–ε are such that dM(n)(x, y)  ‖fn(x) – fn(y)‖1–ε  α(n)dM(n)(x, y) for all x, y ∊ M(n), then necessarily limn→∞ α(n) = ∞.

We study bi-Hölder homeomorphisms between the unit spheres of finite-dimensional normed spaces and use them to obtain better data structures for the high-dimensional Approximate Near Neighbor search (ANN) in general normed spaces. Our main structural result is a finite-dimensional quantitative version of the following theorem of Daher (1993) and Kalton (unpublished). Every d-dimensional normed space X admits a small perturbation Y such that there is a bi-Holder homeomorphism with good parameters between the unit spheres of Y and Z, where Z is a space that is close to ℓ_2^d. Furthermore, the bulk of this article is devoted to obtaining an algorithm to compute the above homeomorphism in time polynomial in d. Along the way, we show how to compute efficiently the norm of a given vector in a space obtained by the complex interpolation between two normed spaces. We demonstrate that, despite being much weaker than bi-Lipschitz embeddings, such homeomorphisms can be efficiently utilized for the ANN problem. Specifically, we give two new data structures for ANN over a general d-dimensional normed space, which for the first time achieve approximation d^o(1), thus improving upon the previous general bound O(sqrtd) that is directly implied by John's theorem.

We establish a generic reduction from _nonlinear spectral gaps_ of metric spaces to data-dependent Locality-Sensitive Hashing, yielding a new approach to the high-dimensional Approximate Near Neighbor Search problem (ANN) under various distance functions. Using this reduction, we obtain the following results:

We prove that there is a universal constant $C>0$ with the following property. Suppose that $n\in \mathbb{N}$ and that $\mathsf{A}=(a_{ij})\in M_n(\mathbb{R})$ is a symmetric stochastic matrix. Denote the second-largest eigenvalue of $\mathsf{A}$ by $λ_2(\mathsf{A})$. Then for $\mathrm{\it any}$ finite-dimensional normed space $(X,\|\cdot\|)$ we have $$ \forall\, x_1,\ldots,x_n\in X,\qquad \mathrm{dim}(X)\ge \frac12 \exp\left(C\frac{1-λ_2(\mathsf{A})}{\sqrt{n}}\bigg(\frac{\sum_{i=1}^n\sum_{j=1}^n\|x_i-x_j\|^2}{\sum_{i=1}^n\sum_{j=1}^na_{ij}\|x_i-x_j\|^2}\bigg)^{\frac12}\right). $$ This implies that if an $n$-vertex $O(1)$-expander embeds with average distortion $D\ge 1$ into $X$, then necessarily $\mathrm{dim}(X)\gtrsim n^{c/D}$ for some universal constant $c>0$, thus improving over the previously best-known estimate $\mathrm{dim}(X)\gtrsim (\log n)^2/D^2$ of Linial, London and Rabinovich, strengthening a theorem of Matoušek, and answering a question of Andoni, Nikolov, Razenshteyn and Waingarten.

Separating decompositions of metric spaces are an important randomized clustering paradigm that was formulated by Bartal in [Bar96] and is defined as follows. Given a metric space (X, dx), its modulus of separated decomposability, denoted SEP(X, dx), is the infimum over those σ ∊ (0,∞] such that for every finite subset S ⊆ X and every Δ > 0 there exists a distribution over random partitions P of S into sets of diameter at most Δ such that for every x,y ∊ S the probability that both x and y do not fall into the same cluster of the random partition P is at most σdx (x, y)/Δ. Here we obtain new bounds on SEP(X, ‖·‖x) when (X, ‖· ‖x) is a finite dimensional normed space, yielding, as a special case, that for every n ∊ N. More generally, for every p ∊ [2, ∞]. This improves over the work [CCG+ 98] of Charikar, Chekuri, Goel, Guha, and Plotkin, who obtained this bound when p = 2, yet for p ∊ (2, ∞] they obtained the asymptotically weaker estimate One should note that it was claimed in [CCG+98] that the bound is sharp for every p ∊ [2, ∞], and in particular it was claimed in [CCG+98] that However, the above results show that this claim of [CCG+98] is incorrect for every p ∊ (2, ∞]. Our new bounds on the modulus of separated decomposability rely on extremal results for orthogonal hyperplane projections of convex bodies, specifically using the work [BN02] of Barthe and the author. This yields additional refined estimates, an example of which is that for every n ∊ ℕ and k ∊ {1,…,n} we have where denotesthe subset of ℝn consisting of all those vectors that have at most k nonzero entries, equipped with the Euclidean metric. The above statements have implications to the Lip- schitz extension problem through its connection to random partitions that was developed by Lee and the author in [LN04, LN05]. Given a metric space (X,dx), let e(X) denote the infimum over those K ∊ (0, ∞] such that for every Banach space Y and every subset S ⊆ X, every 1-Lipschitz function f : S → Y has a K-Lipschitz extension to all of X. Johnson, Lindenstrauss and Schechtman proved in [JLS86] that e(X) < dim(X) for every finite dimensional normed space (X, ‖ · ‖x). It is a longstanding open problem to determine the correct asymptotic dependence on dim(X) in this context, with the best known lower bound, due to Johnson and Lindenstrauss [JL84], being that the quantity e(X) must sometimes be at least a constant multiple of In particular, the previously best known upper bound on e(ℓn∞) was the O(n) estimate of [JLS86]. It is shown here that for every n ∊ ℕ we have thus answering (up to logarithmic factors) a question that was posed by Brudnyi and Brudnyi in [BB05, Problem 2]. More generally, for every p ∊ [2, ∞], thus resolving (negatively) a conjecture of Brudnyi and Brudnyi in [BB05, Conjecture 5].

We prove that the integrality gap of the Goemans-Linial semidefinite programming relaxation for the Sparsest Cut Problem is Ω(√logn) on inputs with n vertices, thus matching the previously best known upper bound (logn)1/2+o(1) up to lower-order factors. This statement is a consequence of the following new isoperimetric-type inequality. Consider the 8-regular graph whose vertex set is the 5-dimensional integer grid ℤ5 and where each vertex (a,b,c,d,e)∈ ℤ5 is connected to the 8 vertices (a± 1,b,c,d,e), (a,b± 1,c,d,e), (a,b,c± 1,d,e± a), (a,b,c,d± 1,e± b). This graph is known as the Cayley graph of the 5-dimensional discrete Heisenberg group. Given Ω⊆ ℤ5, denote the size of its edge boundary in this graph (a.k.a. the horizontal perimeter of Ω) by |∂hΩ|. For t ϵ ℕ, denote by |∂vtΩ| the number of (a,b,c,d,e)ϵ ℤ5 such that exactly one of the two vectors (a,b,c,d,e),(a,b,c,d,e+t) is in Ω. The vertical perimeter of Ω is defined to be |∂vΩ|= √Σt=1∞|∂vtΩ|2/t2. We show that every subset Ω⊆ ℤ5 satisfies |∂vΩ|=O(|∂hΩ|). This vertical-versus-horizontal isoperimetric inequality yields the above-stated integrality gap for Sparsest Cut and answers several geometric and analytic questions of independent interest.

Transportation cost metrics, also known as the Wasserstein distances W_p, are a natural choice for defining distances between two pointsets, or distributions, and have been applied in numerous fields. From the computational perspective, there has been an intensive research effort for understanding the W_p metrics over R^k, with work on the W_1 metric (a.k.a earth mover distance) being most successful in terms of theoretical guarantees. However, the W_2 metric, also known as the root-mean square (RMS) bipartite matching distance, is often a more suitable choice in many application areas, e.g. in graphics. Yet, the geometry of this metric space is currently poorly understood, and efficient algorithms have been elusive. For example, there are no known non-trivial algorithms for nearest-neighbor search or sketching for this metric. In this paper we take the first step towards explaining the lack of efficient algorithms for the W_2 metric, even over the three-dimensional Euclidean space R^3. We prove that there are no meaningful embeddings of W_2 over R^3 into a wide class of normed spaces, as well as that there are no efficient sketching algorithms for W_2 over R^3 achieving constant approximation. For example, our results imply that: 1) any embedding into L1 must incur a distortion of Omega(sqrt(log(n))) for pointsets of size n equipped with the W_2 metric; and 2) any sketching algorithm of size s must incur Omega(sqrt(log(n))/sqrt(s)) approximation. Our results follow from a more general statement, asserting that W_2 over R^3 contains the 1/2-snowflake of all finite metric spaces with a uniformly bounded distortion. These are the first non-embeddability/non-sketchability results for W_2.

It is shown that there exists a sequence of 3-regular graphs {Gn}∞n=1 and a Hadamard space X such that {Gn}∞n=1 forms an expander sequence with respect to {X{, yet random regular graphs are not expanders with respect to {X{. This answers a question of [31]. {Gn}∞n=1 are also shown to be expanders with respect to random regular graphs, yielding a deterministic sublinear time constant factor approximation algorithm for computing the average squared distance in subsets of a random graph. The proof uses the Euclidean cone over a random graph, an auxiliary continuous geometric object that allows for the implementation of martingale methods.

The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.

It is shown that every measurable partition {A1,..., Ak} of R3 satisfies: ∑i=1k|intAi xe-1/2|x|22dx|22≤ 9π2. Let P1,P2,P3 be the partition of R2 into 120o sectors centered at the origin. The bound (1) is sharp, with equality holding if Ai=Pi x R for i∈ {1,2,3} and Ai=∅ for i∈ {4,...,k}. This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor (FOCS 2008). The proof of (1) reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of (1) is complexity-theoretic: the Unique Games hardness threshold of the Kernel Clustering problem with 4 x 4 centered and spherical hypothesis matrix equals 2π/3.

The classical Grothendieck constant, denoted KG, is equal to the integrality gap of the natural semidefinite relaxation of the problem of computing max {Σi-1mΣj=1naijεiδj: {εi}i=1m, {δj}j=1n⊆{-1,1} } a generic and well-studied optimization problem with many applications. Krivine proved in 1977 that KG ≤ 2log (1+√2)/π and conjectured that his estimate is sharp. We obtain a sharper Grothendieck inequality, showing that KGo>; 0. Our main contribution is conceptual: despite dealing with a binary rounding problem, random 2-dimensional projections combined with a careful partition of ℝ2in order to round the projected vectors, beat the random hyperplane technique, contrary to Krivine's long-standing conjecture.

The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) ∊ (0, 1] such that no matter how we map the vertices of H into ℝd, there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. In [18], motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, it was asked whether or not there exists a sequence {Hn}n=1∞ of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree, for which infn ≥1 c(Hn) > 0. Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of (d + 1)-uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant c = c(d). We also show that, for every d, the best value of the constant c = c(d) that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete (d + 1)-uniform hypergraphs with n vertices, as n → • ∞. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any d and any ε > 0, there exists K = K(ε,d) ≥ d + 1 satisfying the following condition. For any k ≥ K, for any point q ∊ ℝd and for any finite Borel measure μ on ℝd with respect to which every hyperplane has measure 0, there is a partition ℝ = A1 U … U Ak into k measurable parts of equal measure such that all but at most an ε-fraction of the (d + 1)-tuples Ai1, …, Aid+1 have the property that either all simplices with one vertex in each Aij contain q or none of these simplices contain q.

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (aij) with and a (small) k × k symmetric positive semidefinite matrix B = (bij). The goal is to find a partition {S1, …, Sk} of {1, … n} which maximizes . We design a polynomial time approximation algorithm that achieves an approximation ratio of , where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if bij = 〈vi, vj〉 is the Gram matrix representation of B for some v1, …, vk ∊ ℝk then R(B) is the minimum radius of a Euclidean ball containing the points {v1, …, vk}. The parameter C(B) is defined as the maximum over all measurable partitions {A1, …, Ak} of ℝk–1 of the quantity , where for i ∊ {1, …, k} the vector zi ∊ ℝk–1 is the Gaussian moment of Ai, i.e., . We also show that for every ε > 0, achieving an approximation guarantee of is Unique Games hard.

Given a finite regular graph G = (V, E) and a metric space (X, dX), let γ+(G, X) denote the smallest constant γ+ > 0 such that for all f, g: V → X we have: In the special case X = ℝ this quantity coincides with the reciprocal of the absolute spectral gap of G, but for other geometries the parameter γ+(G, X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently. Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of super-expander — a family of bounded-degree graphs Gi = (Vi, Ei), with limi→∞ |Vi| = ∞, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of Gi in any uniformly convex Banach space is Ω(log |Vi|), which is the worst possible behavior due to Bourgain's embedding theorem [3]. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue [11]. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson [28]. We show that non-linear spectral gaps behave sub-multiplicatively under zigzag products — a fact that amounts to a simple iteration of the inequality above. This yields as a special case a very simple (linear algebra free) proof of the Reingold-Vadhan-Wigderson theorem which states that zigzag products preserve the property of having an absolute spectral gap (with quantitative control on the size of the gap). The zigzag iteration of Reingold-Vadhan-Wigderson also involves taking graph powers, which is trivial to analyze in the classical “linear” setting. In our work, the behavior of non-linear spectral gaps under graph powers becomes a major geometric obstacle, and we show that for uniformly convex normed spaces there exists a satisfactory substitute for spectral calculus which makes sense in the non-linear setting. These facts, in conjunction with a variant of Ball's notion of Markov cotype and a Fourier analytic proof of the existence of appropriate “base graphs”, are shown to imply that Reingold-Vadhan-Wigderson type constructions can be carried out in the non-linear setting.

We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap (log n)Ω(1). This is achieved by exhibiting n-point metric spaces of negative type whose L1distortion is (log n)Ω(1). Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to L1when restricted to cosets of the center.

Let X be a normed space that satisfies the Johnson-Lindenstrauss lemma (J-L lemma, in short) in the sense that for any integer n and any x1, …, xn ∊ X there exists a linear mapping L : X → F, where F ⊆ X is a linear subspace of dimension O(log n), such that for all i, j ∊ {1, …, n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion . On the other hand, we show that there exists a normed space Y which satisfies the J-L lemma, but for every n there exists an n-dimensional subspace En ⊆ Y whose Euclidean distortion is at least 2Ω(α(n)), where α is the inverse Ackermann function.

It is shown that a Banach space admits an equivalent norm whose modulus of uniform convexity has power-type p if and only if it is Markov p -convex. Counterexamples are constructed to natural questions related to isomorphic uniform convexity of metric spaces, showing in particular that tree metrics fail to have the dichotomy property.

In the kernel clustering problem we are given a large ntimesn positive semi-definite matrix A=(aij) with Sigmai,jn=1 aij=0 and a small ktimesk positivesemi-definite matrix B=bij. The goal is to find a partition S1,..Skof {1,...n} which maximizes the quantity Sigmai,j=1k(Sigma(i,j)isinSitimesSj). We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm forthis problem, answering a question posed by Song, Smola, Gretton and Borgwardt. In some cases we manage to compute the sharp approximation threshold for this problem assuming the unique games conjecture (UGC). In particular, when B is the 3times3 identity matrix the UGC hardness threshold of this problem is exactly 16pi/27. We present and study a geometricconjecture of independent interest which we show would imply thatthe UGC threshold when B is the ktimesk identity matrix is 8pi/9(1-1/k) for every kges3.

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers $A=\{a_{ijk}\}_{i,j,k=1}^n$ such that for all $i,j,k\in\{1,\dots,n\}$ we have $a_{ijk}=a_{ikj}=a_{kji}=a_{jik}=a_{kij}=a_{jki}$ and $a_{iik}=a_{ijj}=a_{iji}=0$, computes a number $\operatorname{Alg}(A)$ which satisfies with probability at least $\frac12$, $\Omega(\sqrt{\frac{\log n}{n}}t)\cdot\max_{x\in \{-1,1\}^n}\sum_{i,j,k=1}^n a_{ijk}x_ix_jx_k\le\operatorname{Alg}(A)\le\max_{x\in \{-1,1\}^n}\sum_{i,j,k=1}^n a_{ijk}x_ix_jx_k$. On the other hand, we show via a simple reduction from a result of Håstad and Venkatesh [Random Structures Algorithms, 25 (2004), pp. 117–149] that under the assumption $NP\not\subseteq DTIME(n^{(\log n)^{O(1)}})$, for every $\epsilon>0$ there is no algorithm that approximates $\max_{x\in \{-1,1\}^n}\sum_{i,j,k=1}^n a_{ijk}x_ix_jx_k$ within a factor of $2^{(\log n)^{1-\epsilon}}$ in time $2^{(\log n)^{O(1)}}$. Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in $\mathbb{R}^n$ with respect to the $L_1$ norm. We show that it is possible to do so up to a multiplicative error of $O(\sqrt{\frac{n}{\log n}})$, while no randomized polynomial time algorithm can achieve accuracy $o(\sqrt{\frac{n}{\log n}})$. This resolves a question posed by Brieden et al. in [Mathematika, 48 (2001), pp. 63–105]. We apply our new algorithm to improve the algorithm of Håstad and Venkatesh for the Max-E3-Lin-2 problem. Given an overdetermined system $\mathcal{E}$ of N linear equations modulo 2 in $n\le N$ Boolean variables such that in each equation only three distinct variables appear, the goal is to approximate in polynomial time the maximum number of satisfiable equations in $\mathcal{E}$ minus $\frac{N}{2}$ (i.e., we subtract the expected number of satisfied equations in a random assignment). Håstad and Venkatesh obtained an algorithm which approximates this value up to a factor of $O(\sqrt{N})$. We obtain an $O(\sqrt{\frac{n}{\log n}})$ approximation algorithm. By relating this problem to the refutation problem for random $3-CNF$ formulas, we give evidence that obtaining a significant improvement over this approximation factor is likely to be difficult.

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A={aijk}ij,k=1nsuch that for all i,j,kisin{1,...,n} we have aijk=aikj=akji=ajik=akij=akjiand aiik=aijj=aiji=0, computes a number Alg(A) which satisfies with probability at least 1/2, Omega(radic(logn/n))ldrmaxxisin{-1,1}nSigmai,j,k=1naijkxixjxklesAlg(A)lesmaxxisin{-1,1}nSigmai,j,k=1naijkxixjxk. On the other hand, we show via a simple reduction from a result of Hastad and Venkatesh that under the assumption NPnsubeDTIME(n(logn)O(1)),for every epsiv>0 there is no algorithm that approximates maxxisin{-1,1}nSigmai,j,k=1naijkxixjxkwithin a factor of 2(logn)t-epsivin time 2(logn)O(1). Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in Rnwith respect to the L1norm. We show that it is possible to do so up to a multiplicative error of O(radic(n/logn)), while no randomized polynomial time algorithm can achieve accuracy O(radic(n/logn)). This resolves a question posed by Brieden, Gritzmann, Kantian, Klee, Lovasz and Simonos. We apply our new algorithm improve the algorithm of Hastad and Venkatesh or the Max-E3-Lin-2 problem. Given an over-determined system epsiv of N linear equations modulo 2 in nlesN Boolean variables, such that in each equation appear only three distinct variables, the goal is to approximate in polynomial time the maximum number of satisfiable equations in epsiv minus N/2 (i.e. we subtract the expected number of satisfied equations in a random assignment). Hastad and Venkatesh obtained an algorithm which approximates this value up to a factor of O(radicN). We obtain a O(radic(n/logn)) approximation algorithm. By relating this problem to the refutation problem for random 3-CNF formulas we give evidence that obtaining a significant improvement over this approximation factor is likely to be difficult.

Say that a k -CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 − 2 − k + p 2 − k of its clauses (note that every k -CNF formula is 0-satisfiable). Let F k ( n , m ) denote a random k -CNF formula on n variables with m clauses. For every k ≥2 and every r >0 we determine p and δ=δ( k )= O ( k 2 − k /2 ) such that with probability tending to 1 as n →∞, a random k -CNF formula F k ( n , rn ) is p -satisfiable but not ( p +δ)-satisfiable.

We show that any $L_1$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid $\{0,1,\ldots,n\}^2 \subseteq \mathbb{R}^2$ incurs distortion $\Omega \left(\sqrt{\log n}\right)$. We also use Fourier analytic techniques to construct a simple $L_1$ embedding of this space which has distortion $O(\log n)$.

Given a metric space $(X,d_X)$, $c \ge 1$, $r > 0$, and $p,q \in [0,1]$, a distribution over mappings $\mathscr{H} : X \to \mathbb{N}$ is called a $(r,cr,p,q)$-sensitive hash family if any two points in X at distance at most r are mapped by $\mathscr{H}$ to the same value with probability at least p, and any two points at distance greater than $cr$ are mapped by $\mathscr{H}$ to the same value with probability at most q. This notion was introduced by Indyk and Motwani in 1998 as the basis for an efficient approximate nearest neighbor search algorithm and has since been used extensively for this purpose. The performance of these algorithms is governed by the parameter $\rho = \frac{\log(1/p)}{\log(1/q)}$, and constructing hash families with small $\rho$ automatically yields improved nearest neighbor algorithms. Here we show that for $X = \ell_1$ it is impossible to achieve $\rho \le \frac{1}{2c}$. This almost matches the construction of Indyk and Motwani which achieves $\rho \le \frac{1}{c}$.

In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean metrics with low “intrinsic” dimension. Combining the embeddings with known data structures yields the best-known approximate nearest-neighbor data structures for such metrics.

Given a metric space (X,dX), c≥1, r>0, and p,q ≡ [0,1], a distribution over mappings H : X → N is called a (r,cr,p,q)-sensitive hash family if any two points in X at distance at most r are mapped by H to the same value with probability at least p, and any two points at distance greater than cr are mapped by H to the same value with probability at most q. This notion was introduced by Indyk and Motwani in 1998 as the basis for an efficient approximate nearest neighbor search algorithm, and has since been used extensively for this purpose. The performance of these algorithms is governed by the parameter ⊇=log(1/p)/log(1/q), and constructing hash families with small ⊇ automatically yields improved nearest neighbor algorithms. Here we show that for X=l1 it is impossible to achieve ⊇ ≤ 1/2c. This almost matches the construction of Indyk and Motwani which achieves ⊇ ≤ 1/c.

We prove that the function d : Ropf3times Ropf3rarr [0,infin] given by d((x,y,z),(t,u,v)) = ([((t-x)2+(u-y)2)2+ (v-z+2xu-2yt)2]frac12+ (t-x)2+ (u-y)2)frac12is a metric on Ropf3such that (Ropf3,radicd) is isometric to a subset of Hilbert space, yet (Ropf3, d) does not admit a bi-Lipschitz embedding into L1. This yields a new simple counter example to the Goemans-Linial conjecture on the integrality gap of the semidefinite relaxation of the sparsest cut problem. The metric above is doubling, and hence has a padded stochastic decomposition at every scale. We also study the Lpversion of this problem, and obtain a counter example to a natural generalization of a classical theorem of Bretagnolle et al. (1996) (of which the Goemans-Linial conjecture is a particular case). Our methods involve Fourier analytic techniques, and a breakthrough of Cheeger and Kleiner (2006), together with classical results of Pansu (1989) on the differentiability of Lipschitz functions on the Heisenberg group

This paper addresses the non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce and construct optimal Ramsey partitions, and use them to show that for every epsiv isin (0,1), any n-point metric space has a subset of size n1-epsivwhich embeds into Hilbert space with distortion O(1/epsiv). This result is best possible and improves part of the metric Ramsey theorem of Bartal et al. (2005), in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick (2005). Namely, we show that for any n point metric space X, and k ges 1, there exists an O(k)-approximate distance oracle whose storage requirement is O(n1+1k/), and whose query time is a universal constant. We also discuss applications to various other geometric data structures, and the relation to well separated pair decompositions

We show that any L1embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0,1,..., n}2sube Ropf2incurs distortion Omega(radic;(log n)). We also use Fourier analytic techniques to construct a simple L1embedding of this space which has distortion O(log n)

The cut-norm $||A||_C$ of a real matrix $A=(a_{ij})_{i\in R,j\in S}$ is the maximum, over all $I \subset R$, $J \subset S$, of the quantity $|\sum_{i \in I, j\in J} a_{ij}|$. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and we provide an efficient approximation algorithm. This algorithm finds, for a given matrix $A=(a_{ij})_{i\in R,j\in S}$, two subsets $I \subset R$ and $J \subset S$, such that $|\sum_{i \in I, j\in J} a_{ij}| \geq \rho ||A||_C$, where $\rho>0$ is an absolute constant satisfying $\rho >0.56$. The algorithm combines semidefinite programming with a rounding technique based on Grothendieck's inequality. We present three known proofs of Grothendieck's inequality, with the necessary modifications which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson [J. ACM, 42 (1995), pp. 1115-1145], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case.

Various new nonembeddability results (mainly into L/sub 1/) are proved via Fourier analysis. In particular, it is shown that the edit distance on {0, 1}/sup d/ has L/sub 1/ distortion (log d)/sup 1/2 - o(1)/. We also give new lower bounds on the L/sub 1/ distortion of quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

Let NF;(n, k, r) denote the maximum number of columns in an n-row matrix with entries in a finite field F in which each column has at most r nonzero entries and every k columns are linearly independent over F. Such sparse parity check matrices are fundamental tools in coding theory, derandomization and complexity theory. We obtain near-optimal theoretical upper bounds for NF(n, k, r) in the important case k > r, i.e. when the number of correctible errors is greater than the weight. Namely, we show that NF(n, k, r) = O(n(r/2)+(4r/3k)). The best known (probabilistic) lower bound is NF(n, k, r) = Omega(n(r/2)+(r/(2k-2))), while the best known upper bound in the case k > r was for k a power of 2, in which case NF(n, k, r) = Omega(n(r/2)+(1/2)). Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependences in large sets of sparse vectors. In the full version of this paper we present additional applications of this method to problems in combinatorial number theory

We introduce a new graph parameter, called the Grothendieck constant of a graph G=(V,E), which is defined as the least constant K such that for every A:E→R,supf:V→S|V|-1 Σ(u,v) ∈ E A(u,v) · ‹f(u),f(v)› ≤ K supf:V→(-1,+1) Σ(u,v)∈ E A(u,v) · f(u)f(v).The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ∑u,v∈EA(u,v)f(vover all f: V →-1,1, which arises in the study of correlation clustering and in the investigation of the spin glass model. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is O(log θḠ)) where θ(Ḡ) is the Lovasz Theta Function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G. We also show that the maximum possible integrality gap is always at least Ω(log ω(G)), where Ω(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n Θ vertices with no loops is ⏷(log n ). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is ⏷(log n). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth.

We prove that every n-point metric space of negative type (in particular, every n-point subset of L1) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) 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 subset of size k, we achieve an approximation ratio of O(√log k log log k).

We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to J. Bourgain and S. Rao. We prove that any n-point metric space (X, d) embeds in Hilbert space with distortion O(/spl radic//spl alpha//sub X//spl middot/log n), where /spl alpha//sub X/ is a geometric estimate on the decomposability of X. An an immediate corollary, we obtain an O(/spl radic/log /spl lambda//sub X//spl middot/log n) distortion embedding, where /spl lambda//sub X/ is the doubling constant of X. Since /spl lambda//sub X/ /spl les/ n, this result recovers Bourgain 5 theorem, but when the metric X is, in a sense, "low-dimensional", improved bounds are achieved. Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 /spl les/ k /spl les/ n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in /spl lscr//sub /spl infin///sup O(log n)/ with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O(log/sup 2/ n).

For every d > 0, let kd be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n,d/n) is either kd or kd+1 almost surely. If d ∈ (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k+1.

The cut-norm ||A||C of a real matrix A = (aij)i∈R,j∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity | ∑ i∈I,j∈J aij|. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and provide an efficient approximation algorithm. This algorithm finds, for a given matrix A = (aij)i∈R,j∈S, two subsets I ⊂ R and J ⊂ S, such that | ∑ i∈I,j∈J aij | ≥ ρ||A||C, where ρ> 0 is an absolute constant satisfying ρ> 0.56. The algorithm combines semidefinite programming with a rounding technique based on Grothendieck’s Inequality. We present three known proofs of Grothendieck’s inequality, with the necessary modifications which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson [12], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case. 1

Maximum satisfiability is a canonical NP-complete problem that appears empirically hard for random instances. At the same time, it is rapidly becoming a canonical problem for statistical physics. In both of these realms, evaluating new ideas relies crucially on knowing the maximum number of clauses one can typically satisfy in a random k-CNF formula. In this paper we give asymptotically tight estimates for this quantity. Our result gives very tight bounds for the fraction of satisfiable clauses in a random k-CNF. In particular, for k > 2 it improves upon all previously known such bound.

This paper deals with Ramsey-type theorems for metric spaces. Such a theorem states that every n point metric space contains a large subspace which can be embedded with some fixed distortion in a metric space from some special class.Our main theorem states that for any ε>0, every n point metric space contains a subspace of size at least n1-ε which is embeddable in an ultrametric with O(log(1/ε)/ε distortion. This in particular provides a bound for embedding in Euclidean spaces. The bound on the distortion is tight up to the log(1/ε) factor even for embedding in arbitrary Euclidean spaces. This result can be viewed as a non-linear analog of Dvoretzky's theorem, a cornerstone of modern Banach space theory and convex geometry.Our main Ramsey-type theorem and techniques naturally extend to give theorems for classes of hierarchically well-separated trees which have algorithmic implications, and can be viewed as the solution of a natural clustering problem.We further include a comprehensive study of various other aspects of the metric Ramsey problem.

(MATH) In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in \cite{llr}. Let $G$ be a $k$-regular graph, $k \ge 3$, with girth $g$. We show that every embedding $f : G \to \ell_2$ has distortion $\Omega (\sqrt{g})$. The original conjecture which remains open is that the Euclidean distortion is bounded below by $\Omega(g)$. Two proofs are given, one based on semi-definite programming, and the other on Markov Type, a concept that considers random walks on metrics.