Lower Bounds Against PC With Extension Variables
summary
Proves a concrete size lower bound for Polynomial Calculus over F_p (PCR): for every prime p, n and κ = O(log n) there is an explicit unsatisfiable polynomial system on O(n log n) variables of degree O(log n) such that any PCR refutation using M extension variables each depending on ≤ κ originals needs size exp(Ω(n^2/(κ^2·2^κ·(M + n log n)))). Proof uses factored degree and a Sokolov-style splitting of lines, works for one round of k-local extension variables, and relies on robust random-CNF hard instances; it stops short of multiple-round extensions and superquadratic M.
AI-written summary · about
chapters (11)
- 0:00Workshop introduction
- 3:18Workshop program overview
- 6:42Motivation for proof complexity
- 11:06Circuit lower bounds and PC
- 17:54Polynomial calculus basics
- 24:16Challenges with extension variables
- 29:06One-round extension variables in PCR
- 34:11Proof structure and Sokolov’s technique
- 44:07Splitting extension variables
- 49:34High-degree tautologies
- 51:00Open problems and future directions
related talks
01h 00mAverage-case Complexity for Polynomials, and All That
53mNew Lower Bounds and Derandomization for ACC, and a...
01h 01mTrue Complexity of Multilinear Systems
01h 30mInapproximability of Constraint Satisfaction Problems II
55mNon-commutative Computation
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
30mAn Approximate Skolem Function Counter
22mVerifying the Equivalence of Parameterized Quantum Circuits