A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

37 Citations (Scopus)

Abstract

Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, and naturally in non-commutative algebra. In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over Q is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time [1] (whether or not randomization is allowed). The main (simple!) technical contribution of this paper is an analysis of an existing "operator scaling" algorithm due to Gurvits [2], which solved some special cases of the same problem we do (these already include optimization problems like matroid intersection). This analysis of the running time of Gurvits' algorithm combines results from some of these different fields. It lower bounds a parameter of quantum maps called capacity, via degree bounds from algebraic geometry on the Left- Right group action, which in turn is relevant due to certain characterization of the free skew (non-commutative) field. Via the known connections above, our algorithm efficiently solves several problems in different areas which had only exponential-time algorithms prior to this work. These include the "word problem" for the free skew field (namely identity testing for rational expressions over non-commuting variables), testing if a quantum operator is "rank decreasing", and the membership problem in the null-cone of a natural group action arising in Geometric Complexity Theory (GCT). Moreover, extending our algorithm to actually compute the non-commutative rank of a symbolic matrix, yields an efficient factor-2 approximation to the standard commutative rank. This naturally suggests the challenge to improve this approximation factor, noting that a fullypolynomial approximation scheme may lead to a deterministic PIT algorithm. Finally, our algorithm may also be viewed as efficiently solving a family of structured systems of quadratic equations, which seem general enough to encode interesting decision and optimization problems 1.

Original languageEnglish
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE
Pages109-117
Number of pages9
Volume2016-December
ISBN (Electronic)9781509039333
DOIs
Publication statusPublished - 14 Dec 2016
Externally publishedYes
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: 9 Oct 201611 Oct 2016

Conference

Conference57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
CountryUnited States
CityNew Brunswick
Period9/10/1611/10/16

Keywords

  • Derandomization
  • Non-commutative computation
  • Optimization
  • Rational identity testing

Fingerprint

Dive into the research topics of 'A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing'. Together they form a unique fingerprint.

Cite this