Abstract:

The nonlinearity of a Boolean function in n variables is its Hamming distance to the set of all affine Boolean functions in n variables. Boolean functions with large nonlinearity are difficult to approximate by affine Boolean functions, which is of significant interest in cryptography. The largest possible nonlinearity of a Boolean function in n variables also equals the covering radius of the [2^n,n+1] Reed-Muller code, whose determination is a long-standing open problem. It is known that this number is at most 2^{n-1}-2^{n/2-1} and equality holds if and only if n is even. In 1983, Patterson and Wiedemann conjectured that the upper bound is attained also for odd n in an asymptotic sense. In this talk, I will survey the history of this conjecture and then explain how the conjecture can be proved using a mixture of number-theoretic and probabilistic arguments. I will also discuss generalisations of this conjecture.

Kai-Uwe Schmidt is Professor of Mathematics at Paderborn University, Germany. His research interests are algebraic and probabilistic methods in combinatorics. He is a recipient of the 2010 Kirkman medal and the 2018 Hall medal, both awarded by the Institute of Combinatorics and its Applications.