Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-032 | 18th March 2008 00:00

Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates


Authors: Dmitriy Cherukhin
Publication: 18th March 2008 20:26
Downloads: 971


We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed depth $d$, we prove a lower bound $\Omega(n\lambda_{d-1}(n))$ for the size (i.e. the number of wires) of any circuit for computing the cyclic convolution over the field $K$. In particular, for $d=2,3,4$, our bounds are $\Omega(n^{1.5})$, $\Omega(n\log n)$ and $\Omega(n\log\log n)$ respectively; for $d\ge 5$, the function $\lambda_{d-1}(n)$ is slowly growing. On the Boolean model, our bounds are the best known for all even $d$ and for $d=3$. For $d=2,3$, we prove these bounds in previous papers.

ISSN 1433-8092 | Imprint