Another look at degree lower bounds for polynomial calculus

摘要

Polynomial complexity is an algebraic proof system inspired by Grobner bases which was introduced by Clegg, Edmonds and Impagliazzo. Alekhnovich and Razborov devised a method for proving degree lower bounds for polynomial calculus. We present an alternative account of their method, which also encompasses a generalization due to Galesi and Lauria. (C) 2019 Elsevier B.V. All rights reserved.