On the robust hardness of Gröbner basis computation
From MaRDI portal
Publication:1713027
DOI10.1016/j.jpaa.2018.08.016zbMath1408.68071arXiv1511.06436OpenAlexW2963225271MaRDI QIDQ1713027
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
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
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