A deterministic polynomial time algorithm for word problem for the free skew field
Ankit Garg, Princeton University
We study the word problem for the free skew field of non-commutative rational functions. We prove that an existing algorithm due to Gurvits is actually a deterministic polynomial time algorithm for this problem (over the rationals). Our analysis is simple, providing explicit bounds on the "capacity'' measure of totally positive operators introduced by Gurvits.
This problem has a rich history and has appeared in various forms in a remarkable number of mathematical and computational areas. Besides non-commutative algebra, it also has various connections to computational complexity and de-randomization, commutative invariant theory, quantum information theory, system theory, automata and language theory. No special background will be assumed for this talk, as it can be, the problem, algorithm and analysis can be framed in the language of linear algebra. This is joint work with Leonid Gurvits, Rafael Oliveira and Avi Wigderson.