Non-commutative Computation
summary
Survey of concrete results and open problems in non-commutative algebraic complexity: proves exponential formula lower bounds (Nisan-style) for some explicit P-size functions; shows determinant and permanent remain complete under non-commutative linear projections; gives a randomized PIT algorithm via evaluation on matrix tuples; highlights the inversion-height hierarchy (cannot eliminate nested inverses) and a concrete reduction: any superlinear lower bound on the minimal number of squares in a classical sum‑of‑squares identity over C would imply non‑commutative circuit lower bounds for the permanent.
AI-written summary · about
chapters (6)
- 0:00Introduction to complexity
- 3:46Commutative computation
- 9:13Arithmetic complexity results
- 19:23Non-commutative setting
- 28:52Sum of squares and lower bounds
- 37:20Divisions and rational functions
related talks
58mA New Perspective on Commutativity in Verification
29mApproximating the Permanent of Positive Semidefinite Matrices
01h 31mTutorial 1: The GCT Chasm I
01h 01mTrue Complexity of Multilinear Systems
22mNew Lower Bounds and Derandomization for ACC, and a...
23mVerifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach
53mNew Lower Bounds and Derandomization for ACC, and a...
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back