Lower Bounds for Symmetric Circuits for the Determinant

on YouTube ↗43m

" summary

Proves an exponential lower bound for determinant on arithmetic circuits that are symmetric under Alt_n × Alt_n, separating that model from the known polynomial-size Sym_n upper bound. Uses a new support theorem, a generalized bijection game (duplicator wins with Θ(n) pebbles), and a CFI/Cipher‑Imman gadget construction to build 3‑regular bipartite graphs with an odd number of perfect matchings. Shows those graphs give two matrix orderings with opposite determinant sign, forcing all Alt_n×Alt_n‑symmetric circuits computing det to have exponential size.

AI-written summary · about

" chapters (21)

1. 0:00The Elevator Pitch
2. 3:01Arithmetic Circuits
3. 4:00Permanent and Determinant
4. 6:06Restricted Lower Bounds
5. 7:47Previous work on Symmetric Arithmetic Cird
6. 10:56Supports Lower bounds for symmetric circuits rely on the notion of a support.
7. 12:58The Bijection Game
8. 14:15Generalised Bijection Game
9. 16:11The Connection Between the Two
10. 18:17Bringing it All Together
11. 19:18The CFI Construction
12. 22:56Uniform and Non-Uniform Matches Let's consider a non-uniform matching.
13. 23:48Counting Uniform Matches
14. 26:22An Odd Number of Perfect Matchings
15. 29:25Constructing the Graph
16. 31:16Sampling and Expander Graphs
17. 33:33Perfect Matchings and Rank This suffices to get the first three conditions, for the fourth we should also like to show with high probability we can pick a graph with an odd number of matchings.
18. 35:26Putting the Graph Together
19. 36:27Playing Bijection Games
20. 37:33Playing the Game: An Overview
21. 40:24Conclusion