Lower bounds for planar Arithmetic Circuits
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911153769152512 |
|---|---|
| author | Ramya, C. Shastri, Pratik |
| author_facet | Ramya, C. Shastri, Pratik |
| contents | 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 $2n$ 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 $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)$ 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 $Ω(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 (1983) does not hold in the case of planar circuits and formulas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11322 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower bounds for planar Arithmetic Circuits Ramya, C. Shastri, Pratik Computational Complexity 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 $2n$ 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 $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)$ 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 $Ω(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 (1983) does not hold in the case of planar circuits and formulas. |
| title | Lower bounds for planar Arithmetic Circuits |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2509.11322 |