Lower Bounds Against PC With Extension Variables

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=K0nM6IqpGaE


Duration: 55:20
213 views
5

Russell Impagliazzo (UCSD)
https://simons.berkeley.edu/talks/russell-impagliazzo-ucsd-2023-03-20-0
Proof Complexity and Meta-Mathematics

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

Based on the following paper: https://eccc.weizmann.ac.il/report/2022/038/



Other Videos By Simons Institute for the Theory of Computing


2023-03-22Frontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
2023-03-22Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
2023-03-22Towards P≠NP from Extended Frege Lower Bounds
2023-03-22Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
2023-03-22Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
2023-03-21Consistency of NEXP Not in P/poly in a Strong Theory
2023-03-21Lifting to Parity Decision Trees via Stifling (with applications to proof complexity)
2023-03-21A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
2023-03-21The Hitting Proof System
2023-03-21Random log(n)-CNF are Hard for Cutting Planes (Again)
2023-03-20Lower Bounds Against PC With Extension Variables
2023-03-17Strong Bounds for 3-Progressions
2023-03-15The Quantum Fourier Transform Has Small Entanglement | Quantum Colloquium
2023-03-07Writing Workshop with Science Communicator in Residence Adam Becker
2023-02-26What Do the Theory of Computing and the Movies Have in Common?
2023-02-18Unstructured Hardness to Average-Case Randomness
2023-02-18Learning with Distributional Inverters
2023-02-18What (Doesn't) Make Learning Algorithms Generalize?
2023-02-17Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
2023-02-17On Low End Obfuscation and Learning
2023-02-17Average-case Complexity for Polynomials, and All That


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Proof Complexity and Meta-Mathematics
Russell Impagliazzo