I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of this subspace is $o(n)$.

It is not difficult to show that a symmetric function does not satisfy this property by considering a subspace $A=\{x \in \{0,1\}^n \mid x_1 \oplus x_2=1, x_3 \oplus x_4=1, \dots, x_{n-1} \oplus x_n=1\}$. Any $x \in A$ has exactly $n/2$ $1$'s and hence $f$ is constant on the subspace $A$ of dimension $n/2$.

`$2*2^{-2^d}$`

, and the number of $d$-dimensional subspaces is`$\approx 2^{d(n-d)}$`

, so the expected number of constant subspaces is less then $1$ as soon as $d$ is large enough that $2^d > d(n-d)$. (continued) $\endgroup$ – David E Speyer Oct 5 '10 at 13:17