@inproceedings{deshpande2016embedding,
author = {Deshpande, Amit},
title = {Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
year = {2016},
month = {December},
abstract = {Goemans showed that any n points x_1,..., x_n in d-dimensions satisfying l_2^2 triangle inequalities can be embedded into l_[1], with worst-case distortion at most sqrt[d]. We consider an extension of this theorem to the case when the points are approximately low-dimensional as opposed to exactly low-dimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an l_[2]^[2]-to-l_[1] embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns [x_i-x_j]_[i<j]. Average distortion embedding suffices for applications such as the SPARSEST CUT problem. Our embedding gives an approximation algorithm for the SPARSEST CUT problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, in Proc. 17th APPROX, 2014]. Our ideas give a new perspective on l_[2]^[2] metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion sqrt[d].},
publisher = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik},
url = {http://approjects.co.za/?big=en-us/research/publication/embedding-approximately-low-dimensional-l_22-metrics-l_1-2/},
pages = {0.417361111-0.425694444},
volume = {65},
isbn = {978-3-95977-027-9},
edition = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
}