Activities per year
Abstract
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 language  English 

Title of host publication  Mathematical Foundations of Computer Science 2014 
Editors  Erzsébet CsuhajVarjú, Martin Dietzfelbinger, Zoltán Ésik 
Publisher  Springer 
Publication date  2014 
Pages  130140 
ISBN (Print)  9783662444641 
ISBN (Electronic)  9783662444658 
DOIs  
Publication status  Published  2014 
Event  39th International Symposium on Mathematical Foundations of Computer Science  Budapest, Hungary Duration: 25. Aug 2014 → 29. Aug 2014 
Conference
Conference  39th International Symposium on Mathematical Foundations of Computer Science 

Country/Territory  Hungary 
City  Budapest 
Period  25/08/2014 → 29/08/2014 
Series  Lecture Notes in Computer Science 

Volume  8635 
ISSN  03029743 
Fingerprint
Dive into the research topics of 'The Relationship between Multiplicative Complexity and Nonlinearity'. Together they form a unique fingerprint.Related Activities
 1 Organisation or participation in workshops, courses or seminars

39th International Symposium on Mathematical Foundations of Computer Science MFCS 2014
Magnus Gausdal Find (Participant)
25. Aug 2014Activity: Attending an event › Organisation or participation in workshops, courses or seminars