Lower Bounds for Planar Arithmetic Circuits

Arithmetic circuits are a natural well-studied model for computing multivariate polynomials over a field. In this paper, we study planar arithmetic circuits . These are circuits whose underlying graph is planar. In particular, we prove an Ω ( n log n ) lower bound on the size of planar arithmetic circuits computing explicit bilinear forms on 2 n variables. As a consequence, we get an Ω ( n log n ) lower bound on the size of arithmetic formulas and planar algebraic branching programs computing explicit bilinear forms on 2 n 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 Ω ( n 2 ) size lower bounds for computing explicit bilinear forms on 2 n 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 Ω ( n 4/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 Ω ( n 2 /log n ) size lower bound. As a consequence, we demonstrate that there exists an n -variate polynomial computable by an n 1 + 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 Ω ( n 4/3 ) (resp., Ω ( n 2 /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.