On the complexity of computing two nonlinearity measures

Bidragets oversatte titel: On the complexity of computing two nonlinearity measures

Magnus Gausdal Find

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
Bidragets oversatte titelOn the complexity of computing two nonlinearity measures
OriginalsprogEngelsk
TitelComputer Science - Theory and Applications : 9th International Computer Science Symposium in Russia, CSR2014
RedaktørerEdward A. Hirsch, Sergei O. Koznetsov, Jean-Éric Pin, Nikolay K. Vereshchagin
ForlagSpringer
Publikationsdato2014
Sider167-175
ISBN (Trykt)978-3-319-06685-1
ISBN (Elektronisk)978-3-319-06686-8
DOI
StatusUdgivet - 2014
BegivenhedThe 9th International Computer Science Symposium in Russia - Moscow Center for Continuous Mathematical Education, Moskva, Rusland
Varighed: 7. jun. 201411. jun. 2014
Konferencens nummer: 9

Konference

KonferenceThe 9th International Computer Science Symposium in Russia
Nummer9
LokationMoscow Center for Continuous Mathematical Education
LandRusland
ByMoskva
Periode07/06/201411/06/2014
NavnLecture Notes in Computer Science
Vol/bind8476
ISSN0302-9743

Fingeraftryk Dyk ned i forskningsemnerne om 'On the complexity of computing two nonlinearity measures'. Sammen danner de et unikt fingeraftryk.

Citationsformater