Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields
| Autor: | Impagliazzo, Russell, Mouli, Sasank, Pitassi, Toniann |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| DOI: | 10.4230/lipics.ccc.2023.7 |
| Popis: | For every prime p > 0, every n > 0 and κ = O(log n), 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 𝔽_p with M extension variables, each depending on at most κ original variables requires size exp(Ω(n²)/10^κ(M + n log n)) LIPIcs, Vol. 264, 38th Computational Complexity Conference (CCC 2023), pages 7:1-7:24 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|