On the Complexity of Computing Two Nonlinearity Measures

2014/03/03 by Find, Magnus Gausdal
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1403.0417

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ⁿ, 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.

Related

• Multiplicative Complexity of Vector Valued Boolean Functions
• A relation between additive and multiplicative complexity of Boolean functions
• Yet another algorithm to compute the nonlinearity of a Boolean function
• Nonlinearity of Boolean functions: an algorithmic approach based on multivariate polynomials
• On the Incompressibility of Truth With Application to Circuit Complexity