Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913485020987392 |
|---|---|
| author | Jia, He Laddha, Aditi Lee, Yin Tat Vempala, Santosh S. |
| author_facet | Jia, He Laddha, Aditi Lee, Yin Tat Vempala, Santosh S. |
| contents | We show that the volume of a convex body in $\mathbb{R}^{n}$ in the general membership oracle model can be computed to within relative error $\varepsilon$ using $\widetilde{O}(n^{3.5}ψ^{2} + n^3/\varepsilon^{2})$ oracle queries, where $ψ$ is the KLS constant. With the current bound of $ψ=\widetilde{O}(1)$, this gives an $\widetilde{O}(n^{3.5} + n^3/\varepsilon^{2})$ algorithm, improving on the Lovász-Vempala $\widetilde{O}(n^{4}/\varepsilon^{2})$ algorithm from 2003. The main new ingredient is an $\widetilde{O}(n^{3}ψ^{2})$ algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropicize a general convex body. Following this, we can apply the $\widetilde{O}(n^{3}/\varepsilon^{2})$ volume algorithm of Cousins and Vempala for well-rounded convex bodies. We also give an efficient implementation of the new algorithm for convex polytopes defined by $m$ inequalities in $\mathbb{R}^{n}$: polytope volume can be estimated in time $\widetilde{O}(mn^{c}/\varepsilon^{2})$ where $c<3.7$ depends on the current matrix multiplication exponent and improves on the previous best bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_02146 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms Jia, He Laddha, Aditi Lee, Yin Tat Vempala, Santosh S. Data Structures and Algorithms Computational Complexity Functional Analysis We show that the volume of a convex body in $\mathbb{R}^{n}$ in the general membership oracle model can be computed to within relative error $\varepsilon$ using $\widetilde{O}(n^{3.5}ψ^{2} + n^3/\varepsilon^{2})$ oracle queries, where $ψ$ is the KLS constant. With the current bound of $ψ=\widetilde{O}(1)$, this gives an $\widetilde{O}(n^{3.5} + n^3/\varepsilon^{2})$ algorithm, improving on the Lovász-Vempala $\widetilde{O}(n^{4}/\varepsilon^{2})$ algorithm from 2003. The main new ingredient is an $\widetilde{O}(n^{3}ψ^{2})$ algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropicize a general convex body. Following this, we can apply the $\widetilde{O}(n^{3}/\varepsilon^{2})$ volume algorithm of Cousins and Vempala for well-rounded convex bodies. We also give an efficient implementation of the new algorithm for convex polytopes defined by $m$ inequalities in $\mathbb{R}^{n}$: polytope volume can be estimated in time $\widetilde{O}(mn^{c}/\varepsilon^{2})$ where $c<3.7$ depends on the current matrix multiplication exponent and improves on the previous best bound. |
| title | Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms |
| topic | Data Structures and Algorithms Computational Complexity Functional Analysis |
| url | https://arxiv.org/abs/2008.02146 |