Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees
Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees
复制标题
具有受限解析树的非交换算术电路的下界和 PIT
DOI：
--
复制
发表时间：
2018
影响因子：
1.4
通讯作者：
S. Srinivasan
中科院分区：
文献类型：
--
作者：
Guillaume Lagarde;N. Limaye;S. Srinivasan
We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $${mathbb{F}langle{x_1,ldots,x_N
angle}}$$F⟨x1,…,xN⟩, 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.1.We show exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde et al. [Electronic Colloquium on Comput Complexity (ECCC) vol 23, no 94, 2016], who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree. The polynomial we prove a lower bound for is in fact computable by a polynomial-sized non-commutative circuit.2.We show exponential lower bounds for circuits whose parse trees are rotations of a single tree. This simultaneously generalizes recent lower bounds of Limaye et al. (Theory Comput 12(1):1–38, 2016) and the above lower bounds of Lagarde et al. (2016), which are known to be incomparable. Here too, the hard polynomial is computable by a polynomial-sized non-commutative circuit.3.We make progress on a question of Nisan (STOC, pp 410–418, 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)}}$$nΩ(logd) for any UPT formula computing the product of d$${n imes n}$$n×n matrices.When $${d leq log n}$$d≤logn, we can also prove superpolynomial lower bounds for formulas with up to $${2^{o(d)}}$$2o(d) many parse trees (for computing the same polynomial). Improving this bound to allow for $${2^{o(d)}}$$2o(d) trees would give an unconditional separation between ABPs and Formulas.4.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.
We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $${mathbb{F}langle{x_1,ldots,x_N
angle}}$$F⟨x1,…,xN⟩, 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.1.We show exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde et al. [Electronic Colloquium on Comput Complexity (ECCC) vol 23, no 94, 2016], who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree. The polynomial we prove a lower bound for is in fact computable by a polynomial-sized non-commutative circuit.2.We show exponential lower bounds for circuits whose parse trees are rotations of a single tree. This simultaneously generalizes recent lower bounds of Limaye et al. (Theory Comput 12(1):1–38, 2016) and the above lower bounds of Lagarde et al. (2016), which are known to be incomparable. Here too, the hard polynomial is computable by a polynomial-sized non-commutative circuit.3.We make progress on a question of Nisan (STOC, pp 410–418, 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)}}$$nΩ(logd) for any UPT formula computing the product of d$${n imes n}$$n×n matrices.When $${d leq log n}$$d≤logn, we can also prove superpolynomial lower bounds for formulas with up to $${2^{o(d)}}$$2o(d) many parse trees (for computing the same polynomial). Improving this bound to allow for $${2^{o(d)}}$$2o(d) trees would give an unconditional separation between ABPs and Formulas.4.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.
一次读取的不经意算术分支程序之和的确定性身份测试
影响因子：
1.4
作者：
Rohit Gurjar;Arpita Korwar;Nitin Saxena;Thomas Thierauf
通讯作者：
Thomas Thierauf