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


Ankit Garg


Princeton University
Department of Computer Science
35, Olden Street
Princeton, NJ 08544
United States of America


Tuesday, 25 August 2015, 16:00 to 17:00



Abstract: 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).