Tata Institute of Fundamental Research
A Deterministic Polynomial Time Algorithm for Word Problem Over the Free Skew Field
STCS Colloquium
Speaker:
Ankit Garg (Princeton University
Department of Computer Science
35, Olden Street
Princeton, NJ 08544
United States of America)
Organiser:
Umang Bhaskar
Date:
Tuesday, 25 Aug 2015, 16:00 to 17:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Ankit Garg (Princeton University Department of Computer Science 35, Olden Street Princeton, NJ 08544 United States of America) |
| Organiser: | Umang Bhaskar |
| Date: | Tuesday, 25 Aug 2015, 16:00 to 17:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).