论文标题
将各向同性和体积还原为KLS：更快的舍入和音量算法
Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
论文作者
论文摘要
我们表明，使用$ \ wideTilde {o} {o}（n^{3.5} {2} + n^3/qulepsilon use use $ \ varepsiLON $ yisiese $ n $ n $ n $ IS $ IS $ IS $ IS $ IS $ IS $ IS $ n，可以将$ \ mathbb {r}^{n} $中的凸形主体的体积计算为相对错误$ \ VAREPSILON $ n $ \ vAREPSILON $，其中KLS常数。具有$ψ= \ widetilde {o}（1）$的电流界限，这给出了$ \ widetilde {o}（n^{3.5} + n^3/\ varepsilon^{2} {2}）$ algorithm $\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;我们迭代地应用了各向同性的凸体。之后，我们可以将$ \ widetilde {o}（n^{3}/\ varepsilon^{2}）$ cousins和vempala的音量算法应用于全面的凸体。我们还提供了有效实现的新算法，用于$ \ Mathbb {r}^{n} $中$ m $不平等所定义的凸多型的新算法：可以在时间$ \ widetilde {o}（mn^{c} {c}/\ varepsilon^$ c <3. 2} $中估算polytope卷。乘法指数并改善了先前的最佳界限。
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.
