Multiplicative complexity of vector valued Boolean functions

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))m2n AND gates.