On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism

on YouTube ↗31m

" summary

Proves that for any constant D≥3, D-tensor isomorphism reduces in polynomial time to 3-tensor isomorphism, so a large cluster of problems (cubic forms, algebra isomorphism, group-class-2 instances, quantum-state local equivalence) become TI-complete. Reductions use explicit path-algebra quotient constructions plus associative-algebra tools (Jacobson radical, Wedderburn) and Gregor-style graph recovery, and a gadget reduction turns general tensors into lists of skew-symmetric slices to reduce to alternating matrix isometry. Average-case running times drop from q^{n^2} to q^n, worst-case remains essentially brute force.

AI-written summary · about

" chapters (13)

1. 0:00Start
2. 0:20The Problem of Tensor Isomorphism
3. 2:10The Isomorphism Problem for Polynomials for Tensors and for Groups
4. 4:39Group Isomorphism
5. 7:24Tensor Isomorphism
6. 11:03Does It Mean for Two Tensors To Be Isomorphic
7. 17:06Equivalence of Quantum States
8. 18:33Matrix Conjugacy
9. 19:56Results
10. 24:11Reductions
11. 26:30How Do We Reduce Tensor Isomorphism to Alternating Matrix Space Isometry
12. 29:26Tensor Isomorphism over Different Fields
13. 30:22Lattice Isomorphism