Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: http://cstheory.stackexchange.com/questions/1948/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

share|improve this question
1  
I don't understand. If $f$ is the identity, $f(x)=x$ for all $x$, then $f$ isn't constant on any set of more than 1 element. Have you got the codomain wrong? –  Gerry Myerson Oct 5 '10 at 11:46
2  
From your use of $o(n)$ notation, it seems like you are asking for an explicit family of functions $f_n$ for infinitely many integers $n$. Is it standard to call it one function? –  S. Carnahan Oct 5 '10 at 11:52
1  
Maybe the target is supposed to be {0,1}. –  Greg Kuperberg Oct 5 '10 at 12:15
2  
Just to make the obvious observation, a random function has this property. The probability of a random function being constant is $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) –  David Speyer Oct 5 '10 at 13:17
1  
Cross posted on cstheory –  Kaveh Oct 5 '10 at 13:22
show 5 more comments

2 Answers 2

up vote 2 down vote accepted

Unless I am misreading it, the paper Affine dispersers from subspace polynomials by Ben-Sasson and Kopparty gives an explicit construction which is nonconstant on any affine subspace of dimension less than $6 n^{4/5}$.

share|improve this answer
add comment

You can use the explicit affine extractor construction by Bourgain (GAFA 2007). It is almost unbiased on any linear dimension affine subspace of $\{0,1\} ^n$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.