Random zero sets with local growth guarantees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910870308651008 |
|---|---|
| author | Chang, Alan Naor, Assaf Ren, Kevin |
| author_facet | Chang, Alan Naor, Assaf Ren, Kevin |
| contents | We prove that if $(\mathcal{M},d)$ is an $n$-point metric space that embeds quasisymmetrically into a Hilbert space, then for every $τ>0$ there is a random subset $\mathcal{Z}$ of $\mathcal{M}$ such that for any pair of points $x,y\in \mathcal{M}$ with $d(x,y)\ge τ$, the probability that both $x\in \mathcal{Z}$ and $d(y,\mathcal{Z})\ge βτ/\sqrt{1+\log (|B(y,κβτ)|/|B(y,βτ)|)}$ is $Ω(1)$, where $κ>1$ is a universal constant and $β>0$ depends only on the modulus of the quasisymmetric embedding. The proof relies on a refinement of the Arora--Rao--Vazirani rounding technique. Among the applications of this result is that the largest possible Euclidean distortion of an $n$-point subset of $\ell_1$ is $Θ(\sqrt{\log n})$, and the integrality gap of the Goemans--Linial semidefinite program for the Sparsest Cut problem on inputs of size $n$ is $Θ(\sqrt{\log n})$. Multiple further applications are given. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21931 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random zero sets with local growth guarantees Chang, Alan Naor, Assaf Ren, Kevin Metric Geometry Data Structures and Algorithms Functional Analysis We prove that if $(\mathcal{M},d)$ is an $n$-point metric space that embeds quasisymmetrically into a Hilbert space, then for every $τ>0$ there is a random subset $\mathcal{Z}$ of $\mathcal{M}$ such that for any pair of points $x,y\in \mathcal{M}$ with $d(x,y)\ge τ$, the probability that both $x\in \mathcal{Z}$ and $d(y,\mathcal{Z})\ge βτ/\sqrt{1+\log (|B(y,κβτ)|/|B(y,βτ)|)}$ is $Ω(1)$, where $κ>1$ is a universal constant and $β>0$ depends only on the modulus of the quasisymmetric embedding. The proof relies on a refinement of the Arora--Rao--Vazirani rounding technique. Among the applications of this result is that the largest possible Euclidean distortion of an $n$-point subset of $\ell_1$ is $Θ(\sqrt{\log n})$, and the integrality gap of the Goemans--Linial semidefinite program for the Sparsest Cut problem on inputs of size $n$ is $Θ(\sqrt{\log n})$. Multiple further applications are given. |
| title | Random zero sets with local growth guarantees |
| topic | Metric Geometry Data Structures and Algorithms Functional Analysis |
| url | https://arxiv.org/abs/2410.21931 |