Lower Bounds for Planar Arithmetic Circuits
C. Ramya, Pratik Shastri · 2025
Read Lower Bounds for Planar Arithmetic Circuits by C. Ramya, Pratik Shastri (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11322.txt.
Introduction
C. Ramya and Pratik Shastri prove new lower bounds for a restricted circuit type in this 2025 theoretical computer science paper. Arithmetic circuits compute polynomials with additions and multiplications. The authors study circuits whose wiring draws flat. No wires may cross.
Their target is explicit bilinear forms in twice n variables. Any planar circuit needs size growing at least like n log n. The bound carries over to formulas and planar branching programs. It is the first such result for an explicit bilinear form. Read-once planar circuits need quadratically many gates. The paper separates the planar models in fine detail. It also proves stronger bounds for many-output circuits. Computing all first derivatives at once is expensive for planar devices.
Catalog record
| CREATOR | C. Ramya, Pratik Shastri |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-11322
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lower Bounds for Planar Arithmetic Circuits C. Ramya, Pratik Shastri Abstract 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 ) \Omega(n\log n) lower bound on the size of planar arithmetic circuits computing explicit bilinear forms on 2 n 2n variables. As a consequence, we get an Ω ( n log n ) \Omega(n\log n) lower bound on the size of arithmetic formulas and planar algebraic branching programs computing explicit bilinear forms on 2 n 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 Ω ( n 2 ) \Omega(n^{2}) size lower bounds for computing explicit bilinear forms on 2 n 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 Ω ( n 4 / 3 ) \Omega(n^{4/3}) size lower bound for computing an explicit linear transformation on n n -variables. For a suitable definition of multi-output formulas, we extend the above result to get an Ω ( n 2 / log n ) \Omega(n^{2}/\log n) size lower bound. As a consequence, we demonstrate that there exists an n n -variate polynomial computable by an n 1 + o ( 1 ) 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 ) \Omega(n^{4/3}) (resp., Ω ( n 2 / log n ) \Omega(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. 1 Introduction Arithmetic circuits are a natural computational model for computing multivariate polynomials over a field. These are directed acyclic graphs whose in-degree 0 vertices (also known as input gates) are labeled by variables or field constants and whose internal vertices are either addition or multiplication gates. Arithmetic circuits compute polynomials in the natural way and the polynomial computed by the circuit is the one computed at a designated output gate(s). The two important parameters of a circuit are size which is the number of vertices in it and depth which is the length of a longest input to output path. One of the primary goals in Algebraic Complexity Theory is to prove lower bounds on the size of arithmetic circuits computing an explicit polynomial. Despite consistent efforts, the best known size lower bound for the arithmetic circuits is due to Baur and Strassen [ 3 ] who proved that any fan-in 2 circuit computing the polynomial x_{1}^{n}+\cdots+x_{n}^{n} has size \Omega(n\log n) . Arithmetic formulas are circuits where the underlying graph is a tree. Kalarkoti [ 11 ] proved that a certain complexity measure based on the transcendence degree (algebraic rank) of polynomials is a lower bound on the formula size. Using this technique, he proved that the formula complexity of {\sf Det}_{n\times n} , the determinant of the n\times n symbolic matrix, is \Omega(n^{3}) (note that this is an \Omega(m^{3/2}) size lower bound where m=n^{2} is the number of variables of {\sf Det}_{n\times n} ). More recently, Chatterjee et al. [ 8 ] proved that over fields of characteristic greater than 0.1n , any formula computing the elementary symmetric polynomial on n variables of degree 0.1n requires size \Omega(n^{2}) . Algebraic branching programs (ABPs) are yet another model for computing polynomials. ABPs are directed acyclic graphs with designated source and sink vertices and the edges are labeled by variables or constants. The polynomial computed by an ABP is defined to be the sum of weights of all paths from source to sink (where the weight of a path is the product of edge labels in the path). Chatterjee et al. [ 8 ] show that any ABP computing the polynomial x_{1}^{n}+\cdots+x_{n}^{n} has size at least \Omega(n^{2}) . In fact, the results by Chatterjee et al. [ 8 ] also hold for ABPs where the edges are labeled by affine forms. In the regime of polynomials of constant degree, Kalorkoti’s method [ 11 ] can be adapted to give a superlinear lower bounds for formulas computing certain explicit constant degree (in fact, \text{degree}\geq 3 ) polynomials. However, for arithmetic circuits and algebraic branching programs, we do not know any explicit n -variate constant degree polynomial that requires size \Omega(n\log n) . Note that the polynomial x_{1}^{n}+\cdots+x_{n}^{n} for which we know superlinear size lower bounds [ 3 ] has individual degree n . In the case of constant depth arithmetic circuits, Raz [ 21 ] showed that for any constant r and any field \mathbb{F} , there is an explicit n -variate polynomial of total-degree O(r) , with \{0,1\} coefficients such that any depth- r arithmetic circuit for it (using constants from \mathbb{F} ) has size n^{1+\Omega(1)} . Furthermore, Raz [ 21 ] observed that a super-quadratic lower bound of \Omega(n^{2+\epsilon}) for any \epsilon>0 for constant-depth circuits computing an explicit polynomial of constant degree implies an \Omega(n^{1+\epsilon/2}) lower bound for general circuits, a long standing open problem in algebraic complexity theory. Also, recently, Chatterjee et al. [ 7 ] demonstrated that a superlinear lower bound on the size of any ABP for a homogeneous constant-degree polynomial would imply a superlinear lower bound on its determinantal complexity. Bilinear forms are a special and important class of degree two polynomials. These are polynomials of the form {\bf y}^{T}M{\bf x} where {\bf y} and {\bf x} are vectors of n variables each and M\in\mathbb{F}^{n\times n} is a matrix. We say that y^{T}Mx where M\in\mathbb{F}^{n\times n} is explicit if the entries of M can be computed in time {\mathsf{poly}}(n) . In fact, problems such as matrix product, univariate polynomial multiplication are all inherently bilinear in nature and the circuit complexity of bilinear forms is a well-studied notion in algebraic complexity theory. Nisan and Wigderson [ 18 ] initiated a systematic study of the complexity of bilinear forms . A natural model to compute bilinear forms is the model of bilinear circuits . A bilinear circuit is an arithmetic circuit in which every product gate has two inputs, one of which is a linear form in {\bf x} -variables and the other a linear form in {\bf y} -variables. It is well known and easy to prove that any circuit computing a bilinear form can be converted into a bilinear circuit computing the same bilinear form with only constant blowup in size. Therefore, a lower bound for bilinear circuits applies to general circuits as well. The best known lower bound for circuits computing an explicit 2n -variate bilinear form is only \Omega(n) which is linear in the number of variables. This motivates the study of the complexity of bilinear forms in more restricted models such as arithmetic formulas and bounded coefficient models of computation. Nisan and Wigderson [ 18 ] defined the