A. Naor

activity

20032026

most citedA probabilistic approach to the geometry of the \ell_p^n-ball

181 citations · 1.5k across the 84 of their papers we have counts for

collaborators

Showing 2017Show all

4 papers · 1 filter

math.FA2017

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} \to ℓ_{2}$ whose nuclear norm $\|T\|_{\mathsf{S}_1}=\su…

math.MG2017★ 2 cited

A relation between finitary Lipschitz extension moduli

Manor Mendel, Assaf Naor

This short note contains an elementary observation in response to the recent posting arXiv:1707.06593v1, which studies the Lipschitz extension modulus to $n$ additional points. We…

cs.DS2017

The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of $lo g n$

Assaf Naor, Robert Young

We prove that the integrality gap of the Goemans--Linial semidefinite programming relaxation for the Sparsest Cut Problem is $Ω (lo g n)$ on inputs with $n$ vertices.

math.MG2017

Vertical perimeter versus horizontal perimeter

Assaf Naor, Robert Young

The discrete Heisenberg group $H_{Z}^{2 k + 1}$ is the group generated by $a_{1}, b_{1}, \dots, a_{k}, b_{k}, c$ , subject to the relations $[a_{1}, b_{1}] = \dots = [a_{k}, b_{k}] = c$ and $[a…

Impossibility of dimension reduction in the nuclear norm

A relation between finitary Lipschitz extension moduli

The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of logn​

Vertical perimeter versus horizontal perimeter

The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of $lo g n$