<p>I'm going through papers which present algebrization as a barrier and I'm trying to understand how &quot;low-degree&quot; polynomials are precisely defined, i.e. are they low with respect to the characteristic of the finite field(s) in question or just that they are low with respect to the instance size <span class="math-container">$n$</span>?</p>
<p>I get that if we are dealing with fields <span class="math-container">$\mathbb{F}_p$</span> where <span class="math-container">$p=O(2^n)$</span> then we can only possibly deal with polynomials which have degrees <span class="math-container">$O(\text{poly}(n))$</span> because a polynomial of higher degree would require superpolynomial space to describe. In this case the polynomials would be &quot;low&quot; in both of the senses I mentioned above. However, if these fields are <span class="math-container">$\mathbb{F}_q$</span> where <span class="math-container">$q=O(n)$</span> does algebrization also rule out any separation attempts which utilize polynomials with a degree <span class="math-container">$O(\text{poly}(n))$</span>, i.e. cases where the degrees are not low with respect to the field's characteristic but are with respect to the <span class="math-container">$n$</span>?</p>

CC BY-SA 4.0
2021-06-16T15:13:46.117Z
Well, in the original Aaronson–Wigderson paper, it is defined as *constant* multi-degree (meaning $\max_i\deg_{x_i}(p)$). FWIW, they add in a footnote that *all of our results would work equally well if we instead chose to limit $\operatorname{mdeg}(\widetilde A_{m,\mathbb F})$* [the multi-degree] *by a linear or polynomial function of $m$* [the input size].  *On the other hand, nowhere in this paper will $\operatorname{mdeg}(\widetilde A_{m,\mathbb F})$ need to be greater than $2$*.
Emil Jeřábek
CC BY-SA 4.0
2021-06-17T01:59:23.470Z
@EmilJeřábek Thanks. Do you know if the results also follow if the fields also have characteristic which is polynomial in $m$?
Ari
CC BY-SA 4.0
2021-06-17T07:32:08.710Z
Why don’t you look at the paper yourself? The definition asks that there is a low-degree extension for *every* $m$ and *every* finite field $\mathbb F$, so in principle, the field and its characteristic may be arbitrarily large with respect to $m$.
Emil Jeřábek
CC BY-SA 4.0
2021-06-17T20:07:54.083Z
@EmilJeřábek I have read some of the paper (but certainly not all of it).  I am wondering about when the characteristic is small, not arbitrarily large. The definition calls for $|\mathbb{F}|=2^{O(m)}$ but reading some of the proofs more carefully I see the authors mention "for all $\mathbb{F}$" so I guess my question is unfounded.
Ari
<cc.complexity-theory><polynomials><finite-fields><barriers>
How is a "low-degree polynomial" precisely defined in Algebrization?
Ari
# How is a "low-degree polynomial" precisely defined in Algebrization?

(Asked by: username_0 on 2021-06-10)

I'm going through papers which present algebrization as a barrier and I'm trying to understand how "low-degree" polynomials are precisely defined, i.e. are they low with respect to the characteristic of the finite field(s) in question or just that they are low with respect to the instance size $n$?

I get that if we are dealing with fields $\mathbb{F}\_p$ where $p=O(2^n)$ then we can only possibly deal with polynomials which have degrees $O(\text{poly}(n))$ because a polynomial of higher degree would require superpolynomial space to describe. In this case the polynomials would be "low" in both of the senses I mentioned above. However, if these fields are $\mathbb{F}\_q$ where $q=O(n)$ does algebrization also rule out any separation attempts which utilize polynomials with a degree $O(\text{poly}(n))$, i.e. cases where the degrees are not low with respect to the field's characteristic but are with respect to the $n$?

**Tags:** cc.complexity-theory, polynomials, finite-fields, barriers

> **Comments:**
> **username_1**: Well, in the original Aaronson–Wigderson paper, it is defined as *constant* multi-degree (meaning $\max_i\deg_{x_i}(p)$). FWIW, they add in a footnote that *all of our results would work equally well if we instead chose to limit $\operatorname{mdeg}(\widetilde A_{m,\mathbb F})$* [the multi-degree] *by a linear or polynomial function of $m$* [the input size].  *On the other hand, nowhere in this paper will $\operatorname{mdeg}(\widetilde A_{m,\mathbb F})$ need to be greater than $2$*.  
> **username_0**: @EmilJeřábek Thanks. Do you know if the results also follow if the fields also have characteristic which is polynomial in $m$?  
> **username_1**: Why don’t you look at the paper yourself? The definition asks that there is a low-degree extension for *every* $m$ and *every* finite field $\mathbb F$, so in principle, the field and its characteristic may be arbitrarily large with respect to $m$.  
> **username_0**: @EmilJeřábek I have read some of the paper (but certainly not all of it).  I am wondering about when the characteristic is small, not arbitrarily large. The definition calls for $|\mathbb{F}|=2^{O(m)}$ but reading some of the proofs more carefully I see the authors mention "for all $\mathbb{F}$" so I guess my question is unfounded.  

---

## 0 answers

