Another look at degree lower bounds for polynomial calculus

DOI10.1016/j.tcs.2019.09.023zbMath1454.03077OpenAlexW2974433403MaRDI QIDQ2333803

Yuval Filmus

Publication date: 13 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.09.023

zbMATH Keywords

degreelower boundspolynomial calculusproof complexity

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Complexity of proofs (03F20) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Cites Work

• Unnamed Item
• Unnamed Item
• On the automatizability of polynomial calculus
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Optimality of size-degree tradeoffs for polynomial calculus
• Space Complexity in Propositional Calculus
• Long Proofs of (Seemingly) Simple Formulas
• Short proofs are narrow—resolution made simple
• A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs

This page was built for publication: Another look at degree lower bounds for polynomial calculus