Monotone Complexity of Spanning Tree Polynomial Re-visited

on YouTube ↗31m

" summary

Shows that the spanning tree polynomial on theta(N) variables for constant-degree expander families requires monotone circuits of size 2^{Omega(N)}, giving the first strongly exponential lower bound for a PP (set-multilinear) family. Proof combines a set-multilinear structure theorem (writing any small monotone circuit as a sum of nearly balanced product polynomials), expander mixing to bound produced monomials, and a gadget reduction from inner product plus a discrepancy-based correspondence to get epsilon-sensitive lower bounds: for complete graphs the G_epsilon family needs 2^{Omega(N)} size for epsilon >= 2^{-omega(sqrt N)}.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:17Summary
3. 0:36Arithmetic Circuits
4. 1:24Monotone Computation
5. 4:56What is Spanning Tree Polynomial?
6. 7:19Set-multilinear Polynomial
7. 8:07Set-multilinear Monotone Structure Theorem
8. 9:53A Technique to Prove Lower Bound
9. 11:33Basic Question
10. 12:06Arithmetic World: Approach of Hrubes
11. 13:04Some Remark About the Approach
12. 14:05Results on e-Sensitive Monotone Lower Bounds
13. 14:53Spanning Tree Communication Problem
14. 15:38Spanning Tree is Hard Under a Fixed Partition
15. 16:21Reduction
16. 19:561 Instance of IP
17. 23:03The Measure Discrepancy
18. 26:50Global Measure Via Uniform Distribution
19. 27:45Discrepancy-Sensitivity Correspondence
20. 29:42Conclusion and Open Problems