Geodesic
Upper bounds on nonlinearity of correlation immune Boolean functions
Prikladnaâ diskretnaâ matematika, no. 1 (2011), pp. 34-69

Voir la notice de l'article provenant de la source Math-Net.Ru

It is known that $\mathrm{nl}(f)\le 2^{n-1}-2^m$ for the nonlinearity $\mathrm{nl}(f)$ of any Boolean function $f$ with $n$ variables and with the correlation immunity order $m$. We prove that for all $n\ge512$ and $0$, except two cases: $m=2^s$, $n=2^{s+1}+1$ and $m=2^s+1$, $n=2^{s+1}+2$ for $s\ge0$, this bound can be improved up to $\mathrm{nl}(f)\le2^{n-1}-2^{m+1}$. Besides, we have checked this result for $n512$, $0$ using computer.
Keywords: Boolean functions, nonlinearity, correlation immunity. 
@article{PDM_2011_1_a3,
     author = {A. V. Khalyavin},
     title = {Upper bounds on nonlinearity of correlation immune {Boolean} functions},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {34--69},
     publisher = {mathdoc},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/}
}
TY  - JOUR
AU  - A. V. Khalyavin
TI  - Upper bounds on nonlinearity of correlation immune Boolean functions
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 34
EP  - 69
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/
LA  - ru
ID  - PDM_2011_1_a3
ER  - 
%0 Journal Article
%A A. V. Khalyavin
%T Upper bounds on nonlinearity of correlation immune Boolean functions
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 34-69
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/
%G ru
%F PDM_2011_1_a3
A. V. Khalyavin. Upper bounds on nonlinearity of correlation immune Boolean functions. Prikladnaâ diskretnaâ matematika, no. 1 (2011), pp. 34-69. http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/