7
$\begingroup$

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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Emil Jeřábek
    Jun 16, 2021 at 15:13
  • $\begingroup$ @EmilJeřábek Thanks. Do you know if the results also follow if the fields also have characteristic which is polynomial in $m$? $\endgroup$
    – Ari
    Jun 17, 2021 at 1:59
  • $\begingroup$ 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$. $\endgroup$
    – Emil Jeřábek
    Jun 17, 2021 at 7:32
  • $\begingroup$ @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. $\endgroup$
    – Ari
    Jun 17, 2021 at 20:07

0

Reset to default

Your Answer

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