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

We explore new directions in simulating complex computations with low space, building on the work of Williams [STOC'25] and Cook-Mertz [STOC'24, SICOMP'25]. We define and study a strengthened version of the parallel external memory model, in which there are $P$ processors each with private internal memory $M$, all of which ... more >>>

We show that random linear codes possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one controls all translates of a fixed test, and the other controls large families of Fourier-pseudorandom tests. Two motivating applications follow:

First, random linear codes ... more >>>