A Deterministic Polynomial Time Algorithm for Word Problem Over the Free Skew Field

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 introducted 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. I plan to explain some of these connections, as well as the central open problem relating them - the ``fullness dimension''.

No special background will be assumed, as it can be, the problem, algorithm and analysis can be framed in the language of linear algebra (this is joint work with Rafael Oliveira and Avi Wigderson).