Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PLANAR CIRCUITS:
Reports tagged with Planar Circuits:
TR23-202 | 15th December 2023
C Ramya, Pratik Shastri

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 $\Omega(n\log n)$ lower bound on the size of planar arithmetic circuits computing explicit bilinear forms ... more >>>




ISSN 1433-8092 | Imprint