The Relationship between Multiplicative Complexity and Nonlinearity

Joan Boyar, Magnus Gausdal Find

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2014
EditorsErzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik
Publication date2014
ISBN (Print)978-3-662-44464-1
ISBN (Electronic)978-3-662-44465-8
Publication statusPublished - 2014
Event39th International Symposium on Mathematical Foundations of Computer Science - Budapest, Hungary
Duration: 25. Aug 201429. Aug 2014


Conference39th International Symposium on Mathematical Foundations of Computer Science
SeriesLecture Notes in Computer Science


Dive into the research topics of 'The Relationship between Multiplicative Complexity and Nonlinearity'. Together they form a unique fingerprint.

Cite this