Mathematics

Professor Subhamoy Maitra
Indian Statistical Institute, Kolkata

It is well known that the maximum possible nonlinearity of an
$n$-variable function is equal to the covering radius of first order
Reed-Muller code. For even values of $n$, the maximum possible
nonlinearity is known and functions achieving this nonlinearity are called
bent. For odd values of $n$, the problem related to maximum possible
nonlinearity is open for long time, though a few important partial results
are available in the past 50 years. Patterson and Wiedemann showed
that for odd $n\\geq 15$, it is possible to construct functions whose
nonlinearity is greater than that obtained by concatenating two bent
functions. We will survey related results in this talk, our contributions
in this area and the open poblems. These combinatorial problems, in the
domain of Boolean functions, are very easy to understand, though the
solutions are elusive in most of the cases.