This article is cited in 1 paper

Theoretical Foundations of Applied Discrete Mathematics

Nonlinearity statistical properties of Boolean function restrictions on a randomly chosen subspace

A. N. Alekseychuk, S. N. Konyushok

Institute of Special Communications and Protection of Informatics, Kiev, Ukraine

Abstract: It is shown that for all sufficiently large natural $n$, the relative nonlinearity of any Boolean function in $n$ variables can be statistically approximated by the relative nonlinearity of its restriction on a random subspace (possibly without the zero vector), whose dimension is independent on $n$.

Keywords: Boolean functions, nonlinearity, random subspace, statistical estimation.

UDC: 631.391+519.2