English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Goemans showed that any $n$ points $x_1, \dotsc x_n$ in $d$-dimensionssatisfying $\ell_2^2$ triangle inequalities can be embedded into $\ell_{1}$,with worst-case distortion at most $\sqrt{d}$. We extend this to the case whenthe points are approximately low-dimensional, albeit with average distortionguarantees. More precisely, we give an $\ell_{2}^{2}$-to-$\ell_{1}$ embeddingwith average distortion at most the stable rank, $\mathrm{sr}(M)$, of thematrix $M$ consisting of columns $\{x_i-x_j\}_{i<j}$. Average distortionembedding suffices for applications such as the Sparsest Cut problem. Ourembedding gives an approximation algorithm for the \sparsestcut problem on lowthreshold-rank graphs, where earlier work was inspired by Lasserre SDPhierarchy, and improves on a previous result of the first and third author[Deshpande and Venkat, In Proc. 17th APPROX, 2014]. Our ideas give a newperspective on $\ell_{2}^{2}$ metric, an alternate proof of Goemans' theorem,and a simpler proof for average distortion $\sqrt{d}$. Furthermore, while theseminal result of Arora, Rao and Vazirani giving a $O(\sqrt{\log n})$ guaranteefor Uniform Sparsest Cut can be seen to imply Goemans' theorem with averagedistortion, our work opens up the possibility of proving such a result directlyvia a Goemans'-like theorem.

Embedding approximately low-dimensional $\ell_2^2$ metrics into $\ell_1$