Suppose $f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ is a degree $d$ polynomial and $\epsilon>0$ is some real number. Does there necessarily exist a set $C\subset [n]$ of coordinates with the size of $C$ bounded by some function of only $d$ and $\epsilon$ so that if $x_C$ and $x_{\bar{C}}$ are the inputs to $f$ on the coordinates in $C$ and not in $C$, respectively, then with probability at least $1-\epsilon$ over a uniform random choice of $x_{\bar{C}}$, the probability over a random $x_C$ that $f(x_C,x_{\bar{C}})=1$ is within $\epsilon$ of the probability that $f(x)=1$?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, this is known. Chattopadhyay, Hatami, Hosseini, Lovett, and Zuckerman (STOC'20) have shown that there exists a set $C\subseteq [n]$ of size at most $\log(1/\varepsilon)^{d^{O(d)}}$ that satisfies your condition (see Theorem 1.10 or Corollary 1.11 there). The dependence on $d$ is at least exponential in general as exhibited by the Tribes function, see Theorem 9 of this follow-up by Ivanov, Pavlovic, and Viola (CCC'23).
