Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CYCLIC CONVOLUTION:
Reports tagged with cyclic convolution:
TR08-032 | 18th March 2008
Dmitriy Cherukhin

Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates

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 ... more >>>




ISSN 1433-8092 | Imprint