\input zb-basic
\input zb-ioport
\iteman{io-port 06080086}
\itemau{Demenkov, Evgeny}
\itemti{A lower bound on circuit complexity of vector function in $U _{2}$.}
\itemso{Hirsch, Edward A. (ed.) et al., Computer science -- theory and applications. 7th international computer science symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3--7, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-30641-9/pbk). Lecture Notes in Computer Science 7353, 76-80 (2012).}
\itemab
Summary: In 1973, Lamagna and Savage proved the following result. If $f _{j } :\{0,1\}^{n} \rightarrow \{0,1\}$ for $1 \leq j \leq m$ depends on at least two variables and if for $i \neq j, f _{i } \neq f _{j }$ and $f_i \neq \overline{f_j}$, then for any binary basis $\Omega$, $C_{\Omega}(f_1, \ldots f_m) \geq \min\limits_j C_{\Omega}(f_j) + m -1$, where $C _{\Omega }(f)$ is the minimal size of a circuit computing $f$ in the basis $\Omega $. The main purpose of this paper is to give a better lower bound for the following case. Let $f : \{0,1\}^{n} \rightarrow \{0,1\}$ and $f _{i } = f \oplus x _{i }$ for $1 \leq i \leq n$. Assume that $f$ is not a constant after any three substitutions $x _{i } = c _{i }$ for different variables. Then $$C_{U_2}(f_1, \ldots f_n) \geq \min\limits_{i \neq j, c_i, c_j } C_{U_2}(f\mid_{x_i = c_i, x_j = c_j})+2n-O(1),$$ where $U _{2} = B _{2} \setminus { \oplus , \equiv }$. This implies a $7n$ lower bound on the circuit complexity over $U _{2}$ of $f _{1}, \cdots , f _{n }$ if $f$ has circuit complexity at least $5n$.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-30642-6\_8}
\end