ON THE DISTRIBUTION OF BOOLEAN FUNCTION NONLINEARITY

摘要

Nonlinearity is the number of bits which must change in the truth table of a Boolean function to reach the closest affine function. It may be expressed through the maximum of the absolute value of a component in the function's Walsh-Hadamard transform. Concentration of nonlinearity is proved. The derived bounds on the concentration point and tails of the distribution are tighter than the earlier known ones.