8
$\begingroup$

A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This means that $n-d$ linear substitutions of the form $x_i=\bigoplus_{j\neq i}{x_j\cdot b_j}\oplus b_0$, where $b_i\in \{0,1\}$ do not make the function constant.

For example, the inner product function $IP(x_1, y_1, \ldots, x_{n/2}, y_{n/2})=\bigoplus{x_i\cdot y_i}$ is an affine disperser for dimension $\frac{n}{2}+1$.

Using the probabilistic method one can easily show that affine dispersers for dimension $o(n)$ do exist.

Ben-Sasson and Kopparty, Shaltiel showed that there are affine dispersers for dimension $o(n)$ in P.

Let's say that a function $f$ is a $2$-affine disperser for dimension $d$, if it is not constant after $n-d$ substitutions of the form $x_i=b$ and $x_i=x_j\oplus b$, where $b$'s are constants. It is possible to show (Lemma~$4$ in Paturi, Saks, Zane) that almost all polynomials of degree $2$ are $2$-dispersers for dimension $o(n)$ ($k$-wise independent distributions allow us to derandomize the construction to obtain an explicit function).

It seems that this restriction to 'short' substitutions makes it much easier to find explicit affine dispersers. The first question is: do you know a 'simple' argument showing that some 'explicit' function is a $3$-affine disperser for dimension $o(n)$? By this I mean a function $f\in NP$ which does not become a constant even after $n-o(n)$ substitutions of the form $x_i=x_j\oplus x_k\oplus b$.

Let's consider the following extension of affine dispersers. Now we allow linear and 'quadratic' substitutions. We start with a function of $n$ variables. Then we make a substitution of the form $x_i=\bigoplus_{j\neq i}{x_j\cdot b_j}\oplus b_0$ or $x_i=(x_j\oplus b_j)\cdot(x_k\oplus b_k)\oplus b$, s.t. the substitution makes it a function of $n-1$ variables (i.e., after substituting $x_i$, it will never appear in the subsequent substitutions). We make $n-k$ substitutions as above and require the resulting function of $k$ variables to be non-constant. Again, the probabilistic argument shows that these functions exist for dimension $k=o(n)$. My main question is whether it is possible to find dispersers of this kind for dimension $o(n)$ in NP?

If it helps, we may consider functions with $o(n)$ outputs rather than functions outputting one bit only.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.