Abstract:
The paper is focused on realization of parity functions by circuits in the basis $U_\infty$. This basis contains all functions of the form $x_1^{\sigma_1}\&\ldots\& x_k^{\sigma_k}$. It is proved that every circuit over $U_\infty$ computing a parity function of $n$ variables contains at least $2\frac{1}{9}n+\Theta(1)$ gates.
Fulltext:
PDF file (521 kB)