__
Revision #1 to TR22-038 | 14th March 2022 08:55
__
#### Lower bounds for Polynomial Calculus with extension variables over finite fields

**Abstract:**
For every prime p > 0, every n > 0 and \kappa = O(logn), we show the existence of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(log n) such that any Polynomial Calculus refutation over F_p with M extension variables, each depending on at most \kappa original variables requires size exp(\Omega(n2/(\kappa^2*2^\kappa(M+nlog(n))))) .

**Changes to previous version:**
Fixed the abstract

__
TR22-038 | 13th March 2022 14:01
__

#### Lower bounds for Polynomial Calculus with extension variables over finite fields

**Abstract:**
For every prime p > 0, every n > 0 and ? = O(logn), we show the existence

of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(log n) such that any Polynomial Calculus refutation over F_p with M extension variables, each depending on at most ? original variables requires size exp(?????(n2/(?^2*2^?*(M + ????nlog(n))))) .