Loading jsMath...
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