1
$\begingroup$

Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$.

Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$).

Denote $e_i=(0,\dots,0,\underbrace{1}_i,0,\dots,0)$.

Denote $\bar{x}=(x_1,\dots,x_n)\in\{0,1\}^n$.

Denote $\mu(f(\bar{x}))=\{e_i:f(\bar{x})\neq f(e_i)\}$.

Denote $\mu_f=\max_{x\in\{0,1\}^n}|\mu(f(\bar{x}))|$.

Given $c>0$, is there an $n_c>0$ such that $\forall n>n_c$ there will be no $f\in\mathcal{F_n}$ such that $|\mu_f|\leq \log(deg(f))^{c}$?

Is there an $c>0$ there will be no $f\in\mathcal{F_n}$ such that $|\mu_f|\leq (deg(f))^{\frac{1}{c}}$?

$\endgroup$

0

Your Answer

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