Computing The Nc-Rank Via Discrete Convex Optimization On Cat(0) Spaces

on YouTube ↗01h 05m

" summary

Gives a polynomial-time algorithm for NC rank that combines submodular minimization on modular lattices with geodesically convex optimization on non-manifold CAT(0) (orthoscheme) complexes. Implements a splitting proximal point algorithm on the Hadamard-type complex, shows each proximal update reduces to an exact convex quadratic on a Boolean “apartment” (Euclidean cube), and resolves exponential bit-growth by a periodic reduction to finite fields. Algorithm is correct but currently very slow in practice.

AI-written summary · about

" chapters (10)

1. 0:00Talk introduction
2. 3:38Noncommutative Edmonds problem
3. 9:12Submodularity in NC rank
4. 19:24CAT(0) spaces basics
5. 28:57Orthoscheme complexes
6. 38:28Convex optimization on CAT(0)
7. 48:05Advantages and limitations of the algorithm
8. 53:03Reduction to finite fields
9. 58:27Conclusion
10. 58:53Q&A