On the Complexity of Computing Two Nonlinearity Measures

DOI10.1007/978-3-319-06686-8_13MaRDI QIDQ4981157zbMATH OpenOpenAlexFDO

Authors Magnus Find

Publication date 24 June 2014

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.0417

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

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 $2^{O(n)}$ given the truth table of length $2^n$, in fact under the same assumption it is impossible to approximate the multiplicative complexity within a factor of $(2-epsilon{)}^{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.

Recommendations

• scientific article; zbMATH DE number 3917710
• Complexity of nonlinear two-point boundary-value problems
• Linear complexity and related complexity measures
• The complexity of approximating a nonlinear program
• On convex complexity measures
• The relationship between multiplicative complexity and nonlinearity
• A NEW TWO-DIMENSIONAL COMPLEXITY MEASURE
• Complexity of nonuniform computations for certain discrete problems
• Complexity of a class of nonlinear combinatorial problems related to their linear counterparts
• Complexity metric and structural measure on the class of non deterministic matrices

Cited in

(8)

• Multiplicative complexity of vector valued Boolean functions
• The multiplicative complexity of 6-variable Boolean functions
• Boolean functions with multiplicative complexity 3 and 4
• Upper bounds on the multiplicative complexity of symmetric Boolean functions
• On various nonlinearity measures for Boolean functions
• The relationship between multiplicative complexity and nonlinearity
• Four measures of nonlinearity
• scientific article; zbMATH DE number 7301306 (Why is no real title available?)

This page was built for publication: On the Complexity of Computing Two Nonlinearity Measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4981157)