Asymptotically optimal Boolean functions

2017/11/22 by Schmidt, Kai-Uwe
#06E30 #11T71 #94B05 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1711.08215

Abstract

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+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.

Related

• On the Covering Radius of the Second Order Reed-Muller Code of Length 128
• Low-degree tests at large distances
• The Covering Radius of the Third-Order Reed-Muller Code RM(3,7) is 20
• The Covering Radius of the Reed-Muller Code RM(m-4,m) in RM(m-3,m)
• Highly nonlinear functions over finite fields