Tutorial 1: The GCT Chasm I

on YouTube ↗01h 31m

" summary

Claims that a strengthened permanent-versus-determinant conjecture forces derandomization of Noether’s Normalization for the orbit closure of the determinant, moving the problem from current XSPACE/EXPSPACE down to quasi-determinant (quasi-P) under that conjecture and standard tools (GRH, hardness-to-randomness, Kaltofen factorization). Evidence: the orbit boundary contains “bad exterior points” produced by Newton degeneration that cause exponential circuit-size blowup (beyond the known N^2 lower bound), tied to representation-theoretic tame/wild behavior and Milnor–Thom style geometry. Consequences include potential PH collapse if the chasm cannot be crossed.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 1:16The main reference
3. 1:46The beginning of GCT
4. 9:44The permanent vs. determinant problem
5. 16:54What if the GCT chasm cannot be crossed?
6. 19:48Outline of the talk
7. 23:17The orbit closures
8. 24:32The reformulation in terms of orbit closures
9. 26:24What lies on the border of G det(Y)?
10. 52:49Noether's Normalization Lemma [Hilbert]

" related talks

• 55mNon-commutative ComputationAvi Wigderson · Neo-Classical Methods in Discrete Analysis 2013
• 22mNew Lower Bounds and Derandomization for ACC, and a...Lijie Chen · ITCS 2023
• 53mNew Lower Bounds and Derandomization for ACC, and a...Lijie Chen · Lower Bounds, Learning, and Average-Case Complexity
• 53mA Commentary on the Collision of WorldsRahul Santhanam · Lower Bounds, Learning, and Average-Case Complexity
• 29mApproximating the Permanent of Positive Semidefinite MatricesNima Anari · Discrete Optimization via Continuous Relaxation
• 21mBlack-box Constructive Proofs are UnavoidableRyan Williams, Lijie Chen, Tianqi Yang · ITCS 2023
• 51mOn constant T-depth circuitsIsaac Kim · Summer Cluster Final Workshop 2026
• 51mAllender's Conjecture and its Impacts on Meta-ComplexityShuichi Hirahara · Lower Bounds, Learning, and Average-Case Complexity