ECCC-Report TR22-038https://eccc.weizmann.ac.il/report/2022/038Comments and Revisions published for TR22-038en-usMon, 14 Mar 2022 08:55:37 +0200
Revision 1
| Lower bounds for Polynomial Calculus with extension variables over finite fields |
Sasank Mouli,
Russell Impagliazzo,
Toniann Pitassi
https://eccc.weizmann.ac.il/report/2022/038#revision1For 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))))) .Mon, 14 Mar 2022 08:55:37 +0200https://eccc.weizmann.ac.il/report/2022/038#revision1
Paper TR22-038
| Lower bounds for Polynomial Calculus with extension variables over finite fields |
Sasank Mouli,
Russell Impagliazzo,
Toniann Pitassi
https://eccc.weizmann.ac.il/report/2022/038For 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))))) .Sun, 13 Mar 2022 22:03:44 +0200https://eccc.weizmann.ac.il/report/2022/038