PreprintCC BY 4.0arXiv
An FPRAS for Mixed Volumes
Abstract
We design the first fully polynomial-time randomized approximation scheme (FPRAS) to estimate the mixed volume of n arbitrary compact convex sets in ℝn specified by weak membership oracles. This disproves a longstanding conjecture of Gurvits (2009). AI Disclosure The main ideas were generated entirely by GPT 6 Astra. The purpose of this paper is to provide a human-written exposition of the algorithm.
Related
- The Bézout inequality for mixed volumes characterizes simplices
- DISCRETE MIXED VOLUMES AND ALEXANDROV–FENCHEL-TYPE INEQUALITIES
- Approximation algorithm for mixed volumes of a constant number of convex bodies
- Expected mixed volumes of convex hulls of random walks and Lévy processes
- A simplified proof of the FPRAS for counting perfect matchings
BibTeX
@misc{chen2026fpras,
title = {{An $\mathsfFPRAS$ for Mixed Volumes}},
author = {Xiaoyu Chen and Kuikui Liu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01368},
eprint = {2611.01368},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01368},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An FPRAS for Mixed Volumes
AU - Xiaoyu Chen
AU - Kuikui Liu
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01368
UR - https://arxiv.org/abs/2611.01368
AB - We design the first fully polynomial-time randomized approximation scheme (FPRAS) to estimate the mixed volume of n arbitrary compact convex sets in ℝ^n specified by weak membership oracles. This disproves a longstanding conjecture of Gurvits (2009). AI Disclosure The main ideas were generated entirely by GPT 6 Astra. The purpose of this paper is to provide a human-written exposition of the algorithm.
ER -