A Galois-Theoretic Complexity Measure for Solving Systems of Algebraic Equations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910889727229952 |
|---|---|
| author | Duff, Timothy |
| author_facet | Duff, Timothy |
| contents | Motivated by applications of algebraic geometry, we introduce the Galois width, a quantity characterizing the complexity of solving algebraic equations in a restricted model of computation allowing only field arithmetic and adjoining polynomial roots. We explain why practical heuristics such as monodromy give (at least) lower bounds on this quantity, and discuss problems in geometry, optimization, statistics, and computer vision for which knowledge of the Galois width either leads to improvements over standard solution techniques or rules out this possibility entirely. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17884 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Galois-Theoretic Complexity Measure for Solving Systems of Algebraic Equations Duff, Timothy Algebraic Geometry Computational Complexity 12F99, 68W30, 65H14 Motivated by applications of algebraic geometry, we introduce the Galois width, a quantity characterizing the complexity of solving algebraic equations in a restricted model of computation allowing only field arithmetic and adjoining polynomial roots. We explain why practical heuristics such as monodromy give (at least) lower bounds on this quantity, and discuss problems in geometry, optimization, statistics, and computer vision for which knowledge of the Galois width either leads to improvements over standard solution techniques or rules out this possibility entirely. |
| title | A Galois-Theoretic Complexity Measure for Solving Systems of Algebraic Equations |
| topic | Algebraic Geometry Computational Complexity 12F99, 68W30, 65H14 |
| url | https://arxiv.org/abs/2503.17884 |