APPROXIMATION OF PLATEAUED BOOLEAN FUNCTIONS BY MONOMIAL ONES. | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2008. № 1(1).

From the Parseval'sequation we have that if the squared Walsh transform of the Boolean function takes at most one nonzero value then itsWalsh coefficients are equal to 22n-2s for some s ≤ n/2. These functions are called the 2s - order plateaued functions. In the presentpaper we consider the aspects of an approximation of the plateaued functions by monomial ones. We use the representation ofn-variable Boolean functions by polynomials over the field F2n. The necessary conditions for the Boolean functions to have theHamming distance to all bijective monomials taking only three values: 2n-1, 2n-1 ± 2n-s-1, are obtained. The non-existence of thefunctions, satisfying these conditions for such n that 2n - 1 is prime, is shown.