Average-Case Hardness in Proof Complexity
summary
Survey claims average-case refutation of random instances is the right way to prove strong proof-size lower bounds, and it demonstrates concrete tools: encoding k-clique as a CNF, using the planted clique refutation goal, analyzing the constraint-variable incidence graph and its expansion and applying a Delayer–Prover game to get width/degree lower bounds. Known quantitative results include tree-like resolution n^k lower bounds and SOS degree ≳ log n for G(n,1/2); many size lower bounds for stronger systems remain open.
AI-written summary · about