The Relationship Between Multiplicative Complexity and Nonlinearity
Joan Boyar, Magnus Gausdal Find
MFCS 2014.

We consider the relationship between nonlinearity and multiplicative complexity for Boolean functions with multiple outputs, studying how large a multiplicative complexity is necessary and sufficient to provide a desired nonlinearity. For quadratic circuits, we show that there is a tight connection between error correcting codes and circuits computing functions with high nonlinearity. Using known coding theory results, the lower bound proven here, for quadratic circuits for functions with n inputs and n outputs and high nonlinearity, shows that at least 2.32n AND gates are necessary. 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. For general circuits, we exhibit a concrete function with multiplicative complexity at least 2n-3.


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