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

  • $\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 2 days ago
  • $\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 yesterday
  • $\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 yesterday
  • $\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 22 hours ago

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.