Tutorial 5: The GCT Chasm II
summary
Argues concrete steps toward bridging the GCT chasm by linking determinant vs permanent complexity to explicit representation-theoretic gadgets and algorithmic tests. Presents candidate families of representation-theoretic obstructions and describes how to build associated circuits and invariants in polynomial time for several special cases. Gives complexity measures (determinantal complexity, circuit width) and reports which constructions scale as expected and which fail, plus how those failures point to the next technical bottlenecks.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:22Summary of yesterday's tutorial
- 6:46The Equivalence Problem
- 22:45Example 1: The ring of vector invariants
- 24:03Example 2: The ring of matrix invariants
- 26:31Explicit FFT for constant m
- 32:17The high level proof
- 37:34The problem NNL for invariant rings
related talks
01h 01mThe Gospel According to TCS
53mA Commentary on the Collision of Worlds
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
01h 03mThe Classification Program for Counting Problems II
47mNatural Proofs in Algebraic Circuit Complexity
01h 25mInapproximability of Constraint Satisfaction Problems IV
54mConstraints, Gadgets, and Invariants
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems