License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.41
URN: urn:nbn:de:0030-drops-81094
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8109/
Lagarde, Guillaume ;
Limaye, Nutan ;
Srinivasan, Srikanth
Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees
Abstract
We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative 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 non-commutative 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 non-commutative 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 white-box 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 Non-Commutative Arithmetic Circuits with Restricted Parse Trees}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {41:1--41:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-046-0},
ISSN = {1868-8969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8109},
URN = {urn:nbn:de:0030-drops-81094},
doi = {10.4230/LIPIcs.MFCS.2017.41},
annote = {Keywords: Non-commutative Arithemetic circuits, Partial derivatives, restrictions}
}
|
Keywords: |
|
Non-commutative 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 |
