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


Cross-post: <https://cstheory.stackexchange.com/questions/1948/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen>



A Boolean function that is not constant on affine subspaces of large enough dimension
Unless I am misreading it, the paper [Affine dispersers from subspace polynomials](http://web.mit.edu/swastik/www/affine-disperser.pdf) by Ben-Sasson and Kopparty gives an explicit construction which is nonconstant on any affine subspace of dimension less than $6 n^{4/5}$.


