On the robust hardness of Gröbner basis computation

DOI10.1016/j.jpaa.2018.08.016zbMath1408.68071arXiv1511.06436OpenAlexW2963225271MaRDI QIDQ1713027

David Rolnick, Gwen Spencer

Publication date: 24 January 2019

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.06436

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• Chordal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some complexity results for polynomial ideals
• Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach
• Graph-Coloring Ideals
• Degree bounds for Gröbner bases of low-dimensional polynomial ideals
• Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems
• On the power of unique 2-prover 1-round games
• On the hardness of approximating minimization problems
• On the NP-Hardness of Max-Not-2
• Some optimal inapproximability results