| Compression bounds for Lipschitz maps from the Heisenberg group to $L_1$ (2009) | |||||||||
Abstract | |||||||||
| We prove a quantitative bi-Lipschitz nonembedding theorem for the Heisenberg group with its Carnot-Carath\'eodory metric and apply it to give a lower bound on the integrality gap of the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem. | |||||||||
Publication details | |||||||||
| |||||||||