Assaf Naor

STOC Conference 2025 Conference Paper

Optimal Rounding for Sparsest Cut

• Alan Chang
• Assaf Naor
• Kevin Ren

We prove that the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n ≥ 2 is Θ(√log n ). We achieve this by establishing the following geometric/structural result. If ( M , d ) is an n -point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x , y ∈ M with d ( x , y )≥ τ, the probability that both x ∈ Z and d ( y , Z )≥ βτ/√1+log(| B ( y ,κ β τ)|/| B ( y ,β τ)|) is Ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora–Rao–Vazirani rounding technique.

STOC Conference 2021 Conference Paper

A framework for quadratic form maximization over convex sets through nonconvex relaxations

• Vijay Bhattiprolu
• Euiwoong Lee
• Assaf Naor

We investigate the approximability of the following optimization problem. The input is an n × n matrix A =( A ij ) 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 =1 n ∑ j =1 n A ij x i x j =⟨ 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. The underlying geometry of K plays a critical role; we show under commonly used complexity assumptions that polytime constant-approximability necessitates that K has type-2 constant that grows slowly with n . However, we show that even when the type-2 constant is bounded, this problem sometimes exhibits strong hardness of approximation. Thus, even within the realm of type-2 bodies, the approximability landscape is nuanced and subtle. However, the link that we establish between optimization and geometry of Banach spaces allows us to devise a generic algorithmic approach to the above problem. We associate to each convex body a new (higher dimensional) auxiliary set that is not convex, but is approximately convex when K has a bounded type-2 constant. If our auxiliary set has an approximate separation oracle, then we design an approximation algorithm for the original quadratic optimization problem, using an approximate version of the ellipsoid method. Even though our hardness result implies that such an oracle does not exist in general, this new question can be solved in specific cases of interest by implementing a range of classical tools from functional analysis, most notably the deep factorization theory of linear operators. Beyond encompassing the scenarios in the literature for which constant-factor approximation algorithms were found, our generic framework implies that that for convex sets with bounded type-2 constant, constant factor approximability is preserved under the following basic operations: (a) Subspaces, (b) Quotients, (c) Minkowski Sums, (d) Complex Interpolation. This yields a rich family of new examples where constant factor approximations are possible, which were beyond the reach of previous methods. We also show (under commonly used complexity assumptions) that for symmetric norms and unitarily invariant matrix norms the type-2 constant nearly characterizes the approximability of quadratic maximization.

SODA Conference 2019 Conference Paper

The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics

• Subhash Khot
• Assaf Naor

STOC Conference 2018 Conference Paper

Data-dependent hashing via nonlinear spectral gaps

• Alexandr Andoni
• Assaf Naor
• Aleksandar Nikolov
• Ilya P. Razenshteyn
• Erik Waingarten

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: * For _general_ d -dimensional normed spaces and n -point datasets, we obtain a _cell-probe_ ANN data structure with approximation O (log d /ε 2 ), space d O (1) n 1+ε , and d O (1) n ε cell probes per query, for any ε>0. No non-trivial approximation was known before in this generality other than the O (√ d ) bound which follows from embedding a general norm into ℓ 2 . * For ℓ p and Schatten- p norms, we improve the data structure further, to obtain approximation O ( p ) and sublinear query _time_. For ℓ p , this improves upon the previous best approximation 2 O ( p ) (which required polynomial as opposed to near-linear in n space). For the Schatten- p norm, no non-trivial ANN data structure was known before this work. Previous approaches to the ANN problem either exploit the low dimensionality of a metric, requiring space exponential in the dimension, or circumvent the curse of dimensionality by embedding a metric into a ”tractable” space, such as ℓ 1 . Our new generic reduction proceeds differently from both of these approaches using a novel partitioning method.

FOCS Conference 2018 Conference Paper

Hölder Homeomorphisms and Approximate Nearest Neighbors

• Alexandr Andoni
• Assaf Naor
• Aleksandar Nikolov
• Ilya P. Razenshteyn
• Erik Waingarten

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.

SODA Conference 2018 Conference Paper

Impossibility of dimension reduction in the nuclear norm

• Assaf Naor
• Gilles Pisier
• Gideon Schechtman

Let S 1 (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 n o (1) -dimensional linear subspace of S 1. is not even a O (1)-Lipschitz quotient of any subset of any n o (1) -dimensional linear subspace of S 1. Thus, S 1 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 S 1 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 S 1. The challenge is to demonstrate that cannot be faithfully realized in an arbitrary low-dimensional subspace of S 1, while Brinkman and Charikar obtained such an assertion only for subspaces of S 1 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 S 1 is at most a universal constant multiple of.

SODA Conference 2017 Conference Paper

Probabilistic clustering of high dimensional norms

• Assaf Naor

STOC Conference 2017 Conference Paper

The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

• Assaf Naor
• Robert Young

We prove that the integrality gap of the Goemans-Linial semidefinite programming relaxation for the Sparsest Cut Problem is Ω(√log n ) on inputs with n vertices, thus matching the previously best known upper bound (log n ) 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 |∂ v t Ω| 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 ∞ |∂ v t Ω| 2 / t 2 . 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. The theorem stated above is the culmination of a program whose aim is to understand the performance of the Goemans-Linial semidefinite program through the embeddability properties of Heisenberg groups. These investigations have mathematical significance even beyond their established relevance to approximation algorithms and combinatorial optimization. In particular they contribute to a range of mathematical disciplines including functional analysis, geometric group theory, harmonic analysis, sub-Riemannian geometry, geometric measure theory, ergodic theory, group representations, and metric differentiation. This article builds on the above cited works, with the "twist" that while those works were equally valid for any finite dimensional Heisenberg group, our result holds for the Heisenberg group of dimension 5 (or higher) but fails for the 3-dimensional Heisenberg group. This insight leads to our core contribution, which is a deduction of an endpoint L 1 -boundedness of a certain singular integral on ℝ 5 from the (local) L 2 -boundedness of the corresponding singular integral on ℝ 3 . To do this, we devise a corona-type decomposition of subsets of a Heisenberg group, in the spirit of the construction that David and Semmes performed in ℝ n , but with two main conceptual differences (in addition to more technical differences that arise from the peculiarities of the geometry of Heisenberg group). Firstly, the "atoms" of our decomposition are perturbations of intrinsic Lipschitz graphs in the sense of Franchi, Serapioni, and Serra Cassano (plus the requisite "wild" regions that satisfy a Carleson packing condition). Secondly, we control the local overlap of our corona decomposition by using quantitative monotonicity rather than Jones-type β-numbers.

STOC Conference 2013 Conference Paper

Efficient rounding for the noncommutative grothendieck inequality

• Assaf Naor
• Oded Regev 0001
• Thomas Vidick

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.

STOC Conference 2012 Conference Paper

Solution of the propeller conjecture in R 3

• Steven Heilman
• Aukosh Jagannath
• Assaf Naor

It is shown that every measurable partition {A 1 ,..., A k } of R 3 satisfies: ∑ i=1 k |int A i xe -1/2|x| 2 2 dx| 2 2 ≤ 9π 2 . Let P 1 ,P 2 ,P 3 be the partition of R 2 into 120 o sectors centered at the origin. The bound (1) is sharp, with equality holding if A i =P i x R for i∈ {1,2,3} and A i =∅ 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.

SODA Conference 2011 Conference Paper

Overlap properties of geometric expanders

• Jacob Fox
• Mikhail Gromov
• Vincent Lafforgue
• Assaf Naor
• János Pach

FOCS Conference 2011 Conference Paper

The Grothendieck Constant is Strictly Smaller than Krivine's Bound

• Mark Braverman
• Konstantin Makarychev
• Yury Makarychev
• Assaf Naor

The classical Grothendieck constant, denoted K G, is equal to the integrality gap of the natural semidefinite relaxation of the problem of computing max {Σ i-1 m Σ j=1 n a ij ε i δ j: {ε i } i=1 m, {δ j } j=1 n ⊆{-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 KG o >; 0. Our main contribution is conceptual: despite dealing with a binary rounding problem, random 2-dimensional projections combined with a careful partition of ℝ 2 in order to round the projected vectors, beat the random hyperplane technique, contrary to Krivine's long-standing conjecture.

SODA Conference 2010 Conference Paper

Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities

• Subhash Khot
• Assaf Naor

SODA Conference 2010 Conference Paper

Towards a Calculus for Non-Linear Spectral Gaps

• Manor Mendel
• Assaf Naor

FOCS Conference 2009 Conference Paper

A (log n) Omega(1) Integrality Gap for the Sparsest Cut SDP

• Jeff Cheeger
• Bruce Kleiner
• Assaf Naor

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 L 1 distortion is (log n) Ω(1). Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to L 1 when restricted to cosets of the center.

SODA Conference 2009 Conference Paper

The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite

• William B. Johnson 0001
• Assaf Naor

FOCS Conference 2008 Conference Paper

Approximate Kernel Clustering

• Subhash Khot
• Assaf Naor

In the kernel clustering problem we are given a large ntimesn positive semi-definite matrix A=(a ij ) with Sigma i, j n =1 a ij =0 and a small ktimesk positivesemi-definite matrix B=b ij. The goal is to find a partition S 1, .. S k of {1, .. .n} which maximizes the quantity Sigma i, j=1 k (Sigma (i, j)isinS i timesS j ). 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.

SODA Conference 2008 Conference Paper

The UGC hardness threshold of the ℓ p Grothendieck problem

• Guy Kindler
• Assaf Naor
• Gideon Schechtman

FOCS Conference 2007 Conference Paper

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies

• Subhash Khot
• Assaf Naor

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A={a ijk } ij, k=1 n such that for all i, j, kisin{1, .. ., n} we have a ijk =a ikj =a kji =a jik =a kij =a kji and a iik =a ijj =a iji =0, computes a number Alg(A) which satisfies with probability at least 1/2, Omega(radic(logn/n))ldrmax xisin{-1, 1} n Sigma i, j, k=1 n a ijk x i x j x k lesAlg(A)lesmax xisin{-1, 1} n Sigma i, j, k=1 n a ijk x i x j x k. 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 max xisin{-1, 1} n Sigma i, j, k=1 n a ijk x i x j x k within a factor of 2(logn) t-epsiv in time 2 (logn) O(1). Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in 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(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.

FOCS Conference 2006 Conference Paper

Lp metrics on the Heisenberg group and the Goemans-Linial conjecture

• James R. Lee
• Assaf Naor

We prove that the function d: \mathbb{R}^3 \times \mathbb{R}^3 \to [0, \infty ) given by d\left( {(x, y, z), (t, u, v)} \right)= \left( {[((t - x)^2 + (u - y)^2 )^2 + (v - z + 2xu - 2yt)^2 ]^{\frac{1} {2}} + (t - x)^2 + (u - y)^2 } \right)^{\frac{1} {2}}. is a metric on \mathbb{R}^3 such that (\mathbb{R}^3, \sqrt d ) is isometric to a subset of Hilbert space, yet (\mathbb{R}^3, d) does not admit a bi-Lipschitz embedding into L_1. 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 L_p version of this problem, and obtain a counter example to a natural generalization of a classical theorem of Bretagnolle, Dacunha-Castelle and Krivine (of which the Goemans-Linial conjecture is a particular case). Our methods involve Fourier analytic techniques, and a recent breakthrough of Cheeger and Kleiner, together with classical results of Pansu on the differentiability of Lipschitz functions on the Heisenberg group.

SODA Conference 2006 Conference Paper

Metric cotype

• Manor Mendel
• Assaf Naor

FOCS Conference 2006 Conference Paper

Planar Earthmover is not in L_1

• Assaf Naor
• Gideon Schechtman

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, .. ., n} 2 sube Ropf 2 incurs distortion Omega(radic; (log n)). We also use Fourier analytic techniques to construct a simple L 1 embedding of this space which has distortion O(log n)

FOCS Conference 2006 Conference Paper

Ramsey partitions and proximity data structures

• Manor Mendel
• Assaf Naor

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 n 1-epsiv which 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(n 1+1 k/), 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

SODA Conference 2006 Conference Paper

Trees and Markov convexity

• James R. Lee
• Assaf Naor
• Yuval Peres

STOC Conference 2005 Conference Paper

Euclidean distortion and the sparsest cut

• Sanjeev Arora
• James R. Lee
• Assaf Naor

We prove that every n-point metric space of negative type (in particular, every n-point subset of L 1 ) 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).

FOCS Conference 2005 Conference Paper

Nonembeddability theorems via Fourier analysis

• Subhash Khot
• Assaf Naor

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.

STOC Conference 2005 Conference Paper

Quadratic forms on graphs

• Noga Alon
• Konstantin Makarychev
• Yury Makarychev
• Assaf Naor

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,sup f:V→S |V|-1 Σ (u,v) ∈ E A(u,v) · ‹f(u),f(v)› ≤ K sup f: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 ∈ E A ( u,v ) f ( v over 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 Lovász 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.

STOC Conference 2004 Conference Paper

Approximating the cut-norm via Grothendieck's inequality

• Noga Alon
• Assaf Naor

The cut-norm ||A|| C of a real matrix A=(a ij ) i∈ R,j∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity | Σ i ∈ I, j ∈ 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 provide an efficient approximation algorithm. This algorithm finds, for a given matrix A=(a ij ) i ∈ R, j ∈ S , two subsets I ⊂ R and J ⊂ S, such that | Σ i ∈ I, j ∈ J a ij | ≥ ρ ||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.

FOCS Conference 2004 Conference Paper

Measured Descent: A New Embedding Method for Finite Metrics

• Robert Krauthgamer
• James R. Lee
• Manor Mendel
• Assaf Naor

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).

STOC Conference 2004 Conference Paper

The two possible values of the chromatic number of a random graph

• Dimitris Achlioptas
• Assaf Naor

For every d > 0, let k d 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 k d or k d+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.

STOC Conference 2003 Conference Paper

On metric ramsey-type phenomena

• Yair Bartal
• Nati Linial
• Manor Mendel
• Assaf Naor

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 n 1-ε 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.

FOCS Conference 2003 Conference Paper

On the Maximum Satisfiability of Random Formulas

• Dimitris Achlioptas
• Assaf Naor
• Yuval Peres

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.

STOC Conference 2002 Conference Paper

Girth and euclidean distortion

• Nati Linial
• Avner Magen
• Assaf Naor

(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.