<p>Suppose <span class="math-container">$f$</span> is in <span class="math-container">$\mathbb{F}_2[x_1,...,x_n]$</span> with total degree <span class="math-container">$d$</span>. </p>

<blockquote>
  <p>Q. Is there any kind of switching lemma or restriction lemma in which by applying the lemma on <span class="math-container">$f$</span> we can reduce the total degree of <span class="math-container">$f$</span> in a good way? </p>
</blockquote>

CC BY-SA 4.0
2019-07-01T19:03:34.080Z
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.
Jason Gaitonde
CC BY-SA 4.0
2019-07-02T20:14:23.877Z
@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.
Erfan Khaniki
<circuit-complexity><lower-bounds><polynomials>
Switching lemma for polynomials over $\mathbb{F}_2$
Erfan Khaniki
# Switching lemma for polynomials over $\mathbb{F}_2$

(Asked by: username_0 on 2019-06-28)

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?

**Tags:** circuit-complexity, lower-bounds, polynomials
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  

---

## 0 answers

