On the complexity of computing two nonlinearity measures

Magnus Gausdal Find

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

Abstract

We study the computational complexity of two Boolean nonlinearity measures: the nonlinearity and the multiplicative complexity. We show that if one-way 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 contributionOn the complexity of computing two nonlinearity measures
Original languageEnglish
Title of host publicationComputer Science - Theory and Applications : 9th International Computer Science Symposium in Russia, CSR2014
EditorsEdward A. Hirsch, Sergei O. Koznetsov, Jean-Éric Pin, Nikolay K. Vereshchagin
PublisherSpringer
Publication date2014
Pages167-175
ISBN (Print)978-3-319-06685-1
ISBN (Electronic)978-3-319-06686-8
DOIs
Publication statusPublished - 2014
EventThe 9th International Computer Science Symposium in Russia - Moscow Center for Continuous Mathematical Education, Moskva, Russian Federation
Duration: 7. Jun 201411. Jun 2014
Conference number: 9

Conference

ConferenceThe 9th International Computer Science Symposium in Russia
Number9
LocationMoscow Center for Continuous Mathematical Education
CountryRussian Federation
CityMoskva
Period07/06/201411/06/2014
SeriesLecture Notes in Computer Science
Volume8476
ISSN0302-9743

Fingerprint Dive into the research topics of 'On the complexity of computing two nonlinearity measures'. Together they form a unique fingerprint.

Cite this