Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #1
Authors: Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
Accepted on: 14th March 2022 08:55
Downloads: 482
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
Downloads: 442
Keywords: 


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))))) .



ISSN 1433-8092 | Imprint