The Pathset Approach to Formula Lower Bounds

on YouTube ↗34m

" summary

Defines the average-case k-cycle on layered graphs (edges present with probability ≈1/n) and builds a combinatorial model called path set formulas whose gates are unions and joins of small embedding sets. Proves a conversion via random restriction reduction from AC0 and monotone DeMorgan formulas to path-set formulas, and proves path-set formulas require size roughly n^{Ω(log k)} to produce a dense K-cycle set (while simple average-case algorithms give much smaller constructions), so the reduction yields new average-case formula lower bounds for small k.

AI-written summary · about

" chapters (13)

1. 0:00Start
2. 0:08DeMorgan Formulas
3. 0:22Formula Lower Bounds
4. 0:54Where to look for lower bounds?
5. 3:26Average-Case k-CYCLE
6. 6:21Recursive-Doubling Algorithm
7. 7:12Average-Case Upper Bound
8. 11:18Density Constraints
9. 12:40Operations on Pathsets
10. 15:33Pathset Formulas
11. 21:04The "Pathset Technique"
12. 22:46Pathset Lower Bound
13. 24:59Pathset Complexity Lower Bound