A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion

on YouTube ↗27m

" summary

Proves that random m-clause CNFs whose clause-variable bipartite graph is a good boundary expander require Res(k) proofs of exponential size by converting k-DNF derivations to resolution after k rounds of restrictions; improves previous bounds (previously k ≤ sqrt(log n / log log n and limited densities) to larger k in the constant-density regime and to any polynomial density for every constant k with a density-dependent Δ chosen independently of k. Key tools: unique-neighbor expansion, a subgraph-preserving closure that bounds closure size, a closure-covering dichotomy, and a restriction-to-resolution reduction that yields the final exponential lower bound.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 0:28Problem Statement
3. 0:54Proof Systems
4. 3:10KDF Resolution
5. 4:17Random CNF
6. 10:45Restriction
7. 15:15Proof
8. 23:05Questions

" related talks

• 58mRandom Constraint Satisfaction ProblemsNike Sun · Counting Complexity and Phase Transitions Boot Camp
• 01h 07mWhere the Hard Things AreAndrea Montanari · Counting Complexity and Phase Transitions Boot Camp
• 53mNew Lower Bounds and Derandomization for ACC, and a...Lijie Chen · Lower Bounds, Learning, and Average-Case Complexity
• 01h 17mInapproximability of Constraint Satisfaction Problems IIIJohan Håstad · Real Analysis Boot Camp 2013
• 01h 00mAverage-case Complexity for Polynomials, and All ThatEmanuele Viola · Lower Bounds, Learning, and Average-Case Complexity
• 29mExtended Formulations and Information ComplexityAnkur Moitra · Information Theory in Complexity Theory and Combinatorics 2015
• 01h 25mInapproximability of Constraint Satisfaction Problems IVJohan Håstad · Real Analysis Boot Camp 2013
• 01h 09mInformation Theory in Computational Complexity IVJaikumar Radhakrishnan · Information Theory Boot Camp 2015