All reports by Author Dmitriy Cherukhin:

__
TR08-032
| 18th March 2008
__

Dmitriy Cherukhin#### Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates

Dmitriy Cherukhin

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