Abstract
We investigate the power of Noncommutative Arithmetic Circuits, which compute polynomials over the free noncommutative polynomial ring F<x_1,...,x_N>, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse trees that appear in the circuit. Such restrictions capture essentially all noncommutative circuit models for which lower bounds are known. We prove several results about such circuits.
 We show explicit exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde, Malod, and Perifel (ECCC 2016), who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree.
 We show explicit exponential lower bounds for circuits whose parse trees are rotations of a single tree. This simultaneously generalizes recent lower bounds of Limaye, Malod, and Srinivasan (Theory of Computing 2016) and the above lower bounds of Lagarde et al., which are known to be incomparable.
 We make progress on a question of Nisan (STOC 1991) regarding separating the power of Algebraic Branching Programs (ABPs) and Formulas in the noncommutative setting by showing a tight lower bound of n^{Omega(log d)} for any UPT formula computing the product of d n*n matrices.
When d <= log n, we can also prove superpolynomial lower bounds for formulas with up to 2^{o(d)} many parse trees (for computing the same polynomial). Improving this bound to allow for 2^{O(d)} trees would yield an unconditional separation between ABPs and Formulas.
 We give deterministic whitebox PIT algorithms for UPT circuits over any field (strengthening a result of Lagarde et al. (2016)) and also for sums of a constant number of UPT circuits with different parse trees.
BibTeX  Entry
@InProceedings{lagarde_et_al:LIPIcs:2017:8109,
author = {Guillaume Lagarde and Nutan Limaye and Srikanth Srinivasan},
title = {{Lower Bounds and PIT for NonCommutative Arithmetic Circuits with Restricted Parse Trees}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {41:141:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8109},
URN = {urn:nbn:de:0030drops81094},
doi = {10.4230/LIPIcs.MFCS.2017.41},
annote = {Keywords: Noncommutative Arithemetic circuits, Partial derivatives, restrictions}
}
Keywords: 

Noncommutative Arithemetic circuits, Partial derivatives, restrictions 
Collection: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

01.12.2017 