Enumerator Polynomials: Completeness and Intermediate Complexity

on YouTube ↗48m

" summary

Defines “enumerator” polynomials that sum monomials encoding combinatorial objects, gives five concrete families (cliques, Hamilton cycles, perfect matchings, closed walks, 3‑SAT encodings), and proves three things: several of these are intermediate over GF(2) unless ⊕P has small circuits by showing easy Boolean evaluation but algebraic hardness via coefficient extraction; a homomorphism-based polynomial family is complete for VP with polynomial projections; and monotone projections from permanent to some families require exponential blow‑ups, using extension‑complexity lower bounds.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 0:34Hamiltonian cycles
3. 2:00Algebraic computation models: Circuits
4. 2:33Arithmetic Circuit Families
5. 3:19Algebraic Complexity Classes
6. 5:28Algebraic Reductions: Projections
7. 7:18Other Hard Enumerator Polynomials
8. 8:46A remarkable enumerator polynomial
9. 12:56Intermediate Complexity over finite fields
10. 14:08New Intermediate Polynomials!
11. 15:45Clique polynomial, redefined
12. 23:53Why these are intermediate ...
13. 26:12Why Satis intermediate
14. 29:27Why Clow is intermediate
15. 30:08Enumerating Graph Homomorphisms
16. 30:27Enumerator Polynomial for Homomorphisms
17. 32:09Describing our graph families
18. 34:18What's the big deal?
19. 36:23Monotone p-projections
20. 43:28Summary
21. 44:03Future Directions