In this talk, we will look at the problem of constructing highly nonlinear vectorial maps $F: F_2^n \to F_2^m$. Concretely, we want an $F$ and an $A = A(m,n) > 0$ as small as possible, so that for every affine map $L : F_2^n \to F_2^m$ (of the form $L(x)=Mx+b$) we have:
\[ agree(F, L) := | {x \in F_2^n | F(x) = L(x)} | ≤ A. \]
Such questions have been studied by Nyberg (1991,1993), Carlet and Ding (2004,2007), Liu, Mesnager and Chen (2017), Nagy (2025), and Biryukov, Turecek, and Udovenko (2026).
There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is:
\[ A(m,n) = \Theta( 2^{n−m} + 2^{n/2} ), \]
and in particular, is never smaller than 2^{n/2}.
In the talk, we will see how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we will see how to construct for every $\gamma > 0$, a function $F : F^n_2 \to F^m_2$ with $m = O_\gamma(n)$, achieving
\[ A(m,n) \leq (1+\gamma)^n. \]
Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.
This is joint work with Swastik Kopparty and Rishabh Kothary.
Paper link: https://arxiv.org/abs/2610.06362
