Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-094 | 6th June 2016 14:51

Non-commutative computations: lower bounds and polynomial identity testing

RSS-Feed




TR16-094
Authors: Guillaume Lagarde, Guillaume Malod
Publication: 6th June 2016 18:12
Downloads: 1490
Keywords: 


Abstract:

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-
alize 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 iso-
morphic).
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 [17] 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 deterministic polynomial-time algorithm for polynomial identity testing (PIT) on unambiguous circuits over $\mathbb{R}$ and $\mathbb{C}$, thus providing the largest class of circuits so far in a non-commutative setting for which we can derandomize PIT.


Comment(s):

Comment #1 to TR16-094 | 18th July 2016 09:04

Non-commutative computations: lower bounds and polynomial identity testing

Authors: Guillaume Lagarde, Guillaume Malod
Accepted on: 18th July 2016 09:04
Keywords: 


Comment:

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-
alize 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 iso-
morphic).
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 [17] 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 deterministic polynomial-time algorithm for polynomial identity testing (PIT) on unambiguous circuits over $\mathbb{R}$ and $\mathbb{C}$, thus providing the largest class of circuits so far in a non-commutative setting for which we can derandomize PIT.




ISSN 1433-8092 | Imprint