A Galois-Theoretic Complexity Measure for Solving Systems of Algebraic Equations

2025/03/22 by Duff, Timothy
#12F99 #65H14 #68W30 #Algebraic Geometry (math.AG) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2503.17884

Abstract

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.

Related

• Computing Complex Dimension Faster and Deterministically
• Lower Bounds for diophantine Approximation
• Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy
• The complexity of solving Weil restriction systems
• Numerically Computing Galois Groups of Minimal Problems