Welcome to MathOverflow

Question

4

2

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

edited Oct 5 2010 at 14:41

asked Oct 5 2010 at 11:37

Alexander
41●2

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 2010 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 2010 at 11:52

1

Maybe the target is supposed to be {0,1}. – Greg Kuperberg Oct 5 2010 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 2010 at 13:17

1

Cross posted on [cstheory](cstheory.stackexchange.com/questions/1948/…) – Kaveh Oct 5 2010 at 13:22

show 5 more comments

Anindya De · Answer 1 · 2011-09-26 08:23:28Z UTC

1

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$

answered Sep 26 2011 at 8:23

Anindya De
333●1●6

Ryan O'Donnell · Answer 2 · 2011-09-26 09:22:06Z UTC

1

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

answered Sep 26 2011 at 9:22

Ryan O'Donnell
2,351●8●18

A Boolean function that is not constant on affine subspaces of large enough dimension

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.