Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Multiplicative Complexity of Vector Value Boolean Functions

Published

Author(s)

Magnus G. Find, Joan Boyar

Abstract

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 $\Sigma\Pi\Sigma$ 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{m2^n}$ AND gates.
Citation
arXiv e-Print Archive

Keywords

Nonlinearity, multiplicative complexity, circuit

Citation

Find, M. and Boyar, J. (2015), Multiplicative Complexity of Vector Value Boolean Functions, arXiv e-Print Archive, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=919080, https://arxiv.org/abs/1407.6169 (Accessed May 22, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created September 21, 2015, Updated October 2, 2017