Asymptotically optimal Boolean functions

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:164

Article

Schmidt, Kai-Uwe¹ 

[1] Paderborn Univ, Dept Math, Warburger Str 100, D-33098 Paderborn, Germany

关键词: Boolean function;    Covering radius;    Nonlinearity;    Reed-Muller code;   

DOI  :  10.1016/j.jcta.2018.12.005

来源: Elsevier

【 摘 要 】

The largest Hamming distance between a Boolean function in n variables and the set of all affine Boolean functions in n variables is known as the covering radius rho(n), of the [2(n), n + 1] Reed-Muller code. This number determines how well Boolean functions can be approximated by linear Boolean functions. We prove that lim(n ->infinity )2(n/2) - rho(n)/2(n/2-1 )= 1, which resolves a conjecture due to Patterson and Wiedemann from 1983. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free