**Multiplicative Complexity of Vector Valued Boolean Functions***Joan Boyar, Magnus Gausdal Find*

Theoretical Computer Science.

We consider the multiplicative complexity of Boolean functions with multiple
bits of output, studying how large a multiplicative complexity is necessary and
sufficient to provide a desired nonlinearity.
For so-called ΣΠΣ circuits, we show that
there is a tight connection between error correcting codes and circuits
computing functions with high nonlinearity.
Combining this with known coding theory results, we show that functions with n
inputs and n outputs with the highest possible nonlinearity must have at least 2.32n AND gates.
We further show that one cannot prove stronger lower bounds
by only appealing to the nonlinearity of a function;
we show a bilinear circuit
computing a function with almost optimal nonlinearity with
the number of AND gates being exactly the length of such a shortest code.
Additionally we provide a function which, for general circuits, has multiplicative complexity at least 2n-3.
Finally we study the multiplicative complexity of ``almost all'' functions. We show that every function with n bits of input and m bits of output can be computed using at most 2.5(1+o(1))sqrt(m 2^{n}) AND gates.

Last modified: Tue Jun 3 16:48:05 CEST 2014