.png){kind=icon}
.png){kind=icon}
Return
Lower Bounds for Planar Arithmetic Circuits
.png){kind=icon}
PRE
AI
DOI：10.1145/3778858.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Arithmetic circuits are a natural well-studied model for computing multivariate polynomials over a field. In this article, we study planar arithmetic circuits. These are circuits whose underlying graph is planar. In particular, we prove an Q(n log n) lower bound on the size of planar arithmetic circuits computing explicit bilinear forms on 2n variables. As a consequence, we get an Q(n log n) lower bound on the size of arithmetic formulas and planar algebraic branching programs computing explicit bilinear forms on 2n variables. This is the first such lower bound on the formula complexity of an explicit bilinear form. In the case of read-once planar circuits, we show Q(n2) size lower bounds for computing explicit bilinear forms on 2n variables. Furthermore, we prove fine separations between the various planar models of computations mentioned above. In addition to this, we look at multi-output planar circuits and show Q(n4/3) size lower bound for computing an explicit linear transformation on n-variables. For a suitable definition of multi-output formulas, we extend the above result to get an Q(n2/ log n) size lower bound. As a consequence, we demonstrate that there exists an n-variate polynomial computable by an n1+o(1)-sized formula such that any multi-output planar circuit (resp., multi-output formula) simultaneously computing all its first-order partial derivatives requires size Q(n4/3) (resp., Q(n2/ log n)). This shows that a statement analogous to that of Baur, Strassen [3] does not hold in the case of planar circuits and formulas.
Keywords:
Arithmetic circuits
planar graphs
lower bounds
Journal
A
IF:
0.8
Papers:
9
Citations:
0