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

We show that the volume of a convex body in ${\bf R}^{n}$ in the generalmembership oracle model can be computed to within relative error $\varepsilon$using $\widetilde{O}(n^{3}\psi^{2} + n^{3}/\varepsilon^{2})$ oracle queries,where $\psi$ is the KLS constant. With the current bound of$\psi=\widetilde{O}(1)$, this gives an $\widetilde{O}(n^{3}/\varepsilon^{2})$algorithm, improving on the Lov\'{a}sz-Vempala$\widetilde{O}(n^{4}/\varepsilon^{2})$ algorithm from 2003. The main newingredient is an $\widetilde{O}(n^{3}\psi^{2})$ algorithm for isotropictransformation, following which we can apply the$\widetilde{O}(n^{3}/\varepsilon^{2})$ volume algorithm of Cousins and Vempalafor well-rounded convex bodies. We also give an efficient implementation of thenew algorithm for convex polytopes defined by $m$ inequalities in ${\bfR}^{n}$: polytope volume can be estimated in time$\widetilde{O}(mn^{c}/\varepsilon^{2})$ where $c<3.2$ depends on the currentmatrix multiplication exponent; this improves known bounds.

Reducing Isotropy and Volume to KLS: An $O(n^3\psi^2)$ Volume Algorithm