Robert Young

activity

20052023

most citedFilling inequalities for nilpotent groups

21 citations · 98 across the 26 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

math.GR2017

Filling functions of arithmetic groups

Enrico Leuzinger, Robert Young

The Dehn function and its higher-dimensional generalizations measure the difficulty of filling a sphere in a space by a ball. In nonpositively curved spaces, one can construct fill…

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…

Filling functions of arithmetic groups

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$