Suppose $f$ is in $\mathbb{F}_2[x_1,...,x_n]$ with total degree $d$.

Q. Is there any kind of switching lemma or restriction lemma in which by applying the lemma on $f$ we can reduce the total degree of $f$ in a good way?

  • 1
    $\begingroup$ Sorry if I'm missing something, but is there a reason this intuitively seems like it might be possible? For instance, when $f(x)=\sum_{S\subseteq [n]: \vert S\vert=d} x^S$, any restriction that lowers the degree would have to restrict at least $n-d+1$ variables. $\endgroup$ – J.G Jul 1 '19 at 19:03
  • $\begingroup$ @JasonGaitonde: I see. By your example, it seems there is no result of this kind for general polynomial, but it may be possible to have such a result if we have sparser polynomial than your example. You take all of the monomials of the $d$, but if we have some kind of reasonable bound on the number of the whole monomials, it may lead to a reasonable thing. $\endgroup$ – Erfan Khaniki Jul 2 '19 at 20:14

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.