2026-08-20T15:24:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23438 2025-10-02T12:55:08Z ddc:004 open_access

How to Compute the Volume in Low Dimension? Cornelissen, Arjan Apers, Simon Gribling, Sander Query complexity computational geometry quantum computing volume estimation high-precision limit Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arjan Cornelissen and Simon Apers and Sander Gribling 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.61 urn:nbn:de:0030-drops-234381 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.61 eng https://creativecommons.org/licenses/by/4.0/legalcode