5
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ 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? $\endgroup$
    – Gerry Myerson
    Oct 5, 2010 at 11:46
  • 2
    $\begingroup$ 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? $\endgroup$
    – S. Carnahan ♦
    Oct 5, 2010 at 11:52
  • 1
    $\begingroup$ Maybe the target is supposed to be {0,1}. $\endgroup$
    – Greg Kuperberg
    Oct 5, 2010 at 12:15
  • 1
    $\begingroup$ Ooops, I'm sorry, the range is {0,1}, of course. Fixed. Yes, as far as I know, it is standard to say function instead of an infinite sequence of functions, one for each n. It is usually done in circuit complexity, for example. $\endgroup$
    – Alexander S. Kulikov
    Oct 5, 2010 at 12:50
  • 2
    $\begingroup$ 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) $\endgroup$
    – David E Speyer
    Oct 5, 2010 at 13:17

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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