On the degree of ideal membership proofs from uniform families of polynomials over a finite field

zbMath0984.03044MaRDI QIDQ5954264

Jan Krajíček

Publication date: 17 February 2002

Published in: Illinois Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

lower boundideal membershipmodular counting principlepolynomial calculuspolynomials over a finite prime fieldproof degreetabloid moduli

Mathematics Subject Classification ID

Equations in general fields (12E12) Applications of logic to commutative algebra (13L05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Model theory of fields (12L12) Complexity of proofs (03F20)

Related Items (3)

A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Linear gaps between degrees for the polynomial calculus modulo distinct primes ⋮ Bounds in the theory of finite covers

This page was built for publication: On the degree of ideal membership proofs from uniform families of polynomials over a finite field