CJTCS Volume 2019 Article 2

Volume 2019

Article 2

Published by the Department of Computer Science, The University of Chicago.

Non-commutative computations: lower bounds and polynomial identity testing

Guillaume Lagarde
KTH Royal Institute of Technology
School of Electrical Enginering and Computer Science.
glagarde AT kth DOT se

Guillaume Malod
Université de Paris
IMJ-PRG, CNRS
F-75013 Paris, France
malod AT math DOT univ-paris-diderot DOT fr

and

Sylvain Perifel
Université de Paris
IRIF, CNRS
F-75013 Paris, France
sylvain DOT perifel AT irif DOT fr

September 10, 2019

Abstract

In the setting of non-commutative arithmetic computations, we define a class of circuits that generalize algebraic branching programs (ABP). This model is called unambiguous because it captures the polynomials in which all monomials are computed in a similar way (that is, all the parse trees are isomorphic).

We show that unambiguous circuits of polynomial size can compute polynomials that require ABPs of exponential size, and that they are incomparable with skew circuits.

Generalizing a result of Nisan on ABPs, we provide an exact characterization of the complexity of any polynomial in our model, and use it to prove exponential lower bounds for explicit polynomials such as the determinant.

Finally, we give a white-box deterministic polynomial-time algorithm for polynomial identity testing (PIT) on unambiguous circuits over ℜ and ℂ.