Finding short polynomials

• Applicant: Professor Dr. Thomas Kahle
• Subject Area: Mathematics
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 539867459

This project concerns the number of terms of polynomials as a complexity measure. This is an area of commutative algebra that is much less explored than degree-based complexity measures like Castelnuovo-Mumford regularity. As the finiteness results that drive the Gröbner machinery are based on induction on the degree, they often need to be replaced by more synergetic tools to make progress here. We envision that combinatorial data structures like Newton polyhedral and matroids will help us to solve the fundamental problem of this project: Is it algorithmically decidable if an ideal in a polynomial ring contains a short polynomial?

• DFG Programme: Priority Programmes
• Subproject of: SPP 2458: Combinatorial Synergies