Arrow Research search

Author name cluster

Assaf Naor

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

33 papers
1 author row

Possible papers

33

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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)

Details

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

Details

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

Details

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.

Details

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

Details

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.

Details

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.

Details