We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb{F}_2^n \to \mathbb{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: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (of the form $L(x) = Mx + b$) we have:
$$
agree(F,L) ... more >>>

In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t. Our results are
based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector
based PIRs of Yekhanin and Efremenko. Previously ... more >>>