Clique Is Hard on Average for Regular Resolution

on YouTube ↗46m

" summary

Proves that for random G (edge probability just below the K-clique threshold) and K up to n^{1/4}, any regular-resolution refutation of the unary clique encoding has length n^{Ω(K)}, matching the trivial n^{O(K)} brute-force upper bound. Uses the resolution↔read-once branching-program correspondence and a new bottleneck pair accounting argument plus a path distribution that answers 1 with probability n^{-1/2}. Defines a combinatorial clique-denseness property that random graphs satisfy and shows the lower bound is tight for the density range.

AI-written summary · about

" chapters (9)

1. 0:00Start
2. 3:06Resolution refutation
3. 5:07Branching program solving falsified clause problem
4. 7:53Hardness of k-clique for resolution
5. 10:31Candidate hard graph instance
6. 14:06What makes a graph a hard instance?
7. 15:11Proof structure
8. 15:39Proof technique: bottleneck counting Haken 85
9. 21:15Common neighbourhood