An FPTAS for the Volume of a $\mathcal{V}$-polytope ---It is Hard to Compute The Volume of The Intersection of Two Cross-polytopes

Ei Ando, Shuji Kijima

Given an $n$-dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio $(n/…