Activities per year
Abstract
We study the computational complexity of two Boolean nonlinearity measures: the nonlinearity and the multiplicative complexity. We show that if oneway functions exist, no algorithm can compute the multiplicative complexity in time 2O(n) given the truth table of length 2n, in fact under the same assumption it is impossible to approximate the multiplicative complexity within a factor of (2−ϵ)n/2. When given a circuit, the problem of determining the multiplicative complexity is in the second level of the polynomial hierarchy. For nonlinearity, we show that it is #P hard to compute given a function represented by a circuit.
Translated title of the contribution  On the complexity of computing two nonlinearity measures 

Original language  English 
Title of host publication  Computer Science  Theory and Applications : 9th International Computer Science Symposium in Russia, CSR2014 
Editors  Edward A. Hirsch, Sergei O. Koznetsov, JeanÉric Pin, Nikolay K. Vereshchagin 
Publisher  Springer 
Publication date  2014 
Pages  167175 
ISBN (Print)  9783319066851 
ISBN (Electronic)  9783319066868 
DOIs  
Publication status  Published  2014 
Event  The 9th International Computer Science Symposium in Russia  Moscow Center for Continuous Mathematical Education, Moskva, Russian Federation Duration: 7. Jun 2014 → 11. Jun 2014 Conference number: 9 
Conference
Conference  The 9th International Computer Science Symposium in Russia 

Number  9 
Location  Moscow Center for Continuous Mathematical Education 
Country  Russian Federation 
City  Moskva 
Period  07/06/2014 → 11/06/2014 
Series  Lecture Notes in Computer Science 

Volume  8476 
ISSN  03029743 
Fingerprint Dive into the research topics of 'On the complexity of computing two nonlinearity measures'. Together they form a unique fingerprint.
Related Activities
 1 Talks and presentations in private or public companies

Computer Science  Theory and Applications: 9th International Computer Science Symposium in Russia, CSR2014
Magnus Gausdal Find (Lecturer)
7. Jun 2014Activity: Talks and presentations › Talks and presentations in private or public companies