Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR22-038 | 14th March 2022 08:55

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

Revision #1
Authors: Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
Accepted on: 14th March 2022 08:55
Keywords:

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

### Paper:

TR22-038 | 13th March 2022 14:01

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

TR22-038
Authors: Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
Publication: 13th March 2022 22:03