Asymptotically optimal Boolean functions
Asymptotically optimal Boolean functions
复制标题
DOI：
10.1016/j.jcta.2018.12.005
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
K. Schmidt
中科院分区：
文献类型：
--
作者：
K. Schmidt
一个n元布尔函数和所有n元仿射布尔函数的集合之间的最大汉明距离称为[2 n，n+ 1] Reed-Muller码的覆盖半径ρ n。这个数字决定了布尔函数可以用线性布尔函数近似的程度。证明了lim n→∞ <$2 n/2− ρ n/2 n/2− 1= 1，解决了Patterson和Wiedemann在1983年提出的一个猜想。
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 ρ 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→∞ 2 n/2− ρ n/2 n/2− 1= 1, which resolves a conjecture due to Patterson and Wiedemann from 1983.