How to compute the volume in low dimension?
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912257692139520 |
|---|---|
| author | Cornelissen, Arjan Apers, Simon Gribling, Sander |
| author_facet | Cornelissen, Arjan Apers, Simon Gribling, Sander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02207 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How to compute the volume in low dimension? Cornelissen, Arjan Apers, Simon Gribling, Sander Quantum Physics Computational Complexity 68Q12, 65D18 F.2.2 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. |
| title | How to compute the volume in low dimension? |
| topic | Quantum Physics Computational Complexity 68Q12, 65D18 F.2.2 |
| url | https://arxiv.org/abs/2503.02207 |