<p>recently multivariate polynomial factoring has been <a href="http://eccc.hpi-web.de/report/2014/001/" rel="nofollow">related</a> to <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma#Comparison_of_two_polynomials" rel="nofollow">Polynomial Identity Testing / PIT</a> (by Kopparty, Saraf, Shpilka). </p>

<blockquote>
  <p>where is the complexity of factoring multivariate polynomials over <a href="http://en.wikipedia.org/wiki/Finite_field" rel="nofollow">finite fields</a> analyzed/ surveyed, in particular for <strong>F<sub>2</sub></strong>?</p>
</blockquote>

<p>(eg is there a complete problem related to that, or does KSS result relate to factorization over finite fields etc?)</p>

CC BY-SA 3.0
2015-04-20T04:18:27.833Z
A quick web search reveals many sources, and there are also several monographs I can think of that answer your question. Have you looked at these sources?
Yuval Filmus
CC BY-SA 3.0
2015-04-20T04:55:56.393Z
I think they reduce factoring to PIT. Is there a reverse connection?
Turbo
<cc.complexity-theory><reference-request><polynomials>
complexity of factoring multivariate polynomials over Fn
vzn
# complexity of factoring multivariate polynomials over Fn

(Asked by: username_0 on 2015-04-20)

recently multivariate polynomial factoring has been [related](http://eccc.hpi-web.de/report/2014/001/) to [Polynomial Identity Testing / PIT](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma#Comparison_of_two_polynomials) (by Kopparty, Saraf, Shpilka).

> where is the complexity of factoring multivariate polynomials over [finite fields](http://en.wikipedia.org/wiki/Finite_field) analyzed/ surveyed, in particular for **F2**?

(eg is there a complete problem related to that, or does KSS result relate to factorization over finite fields etc?)

**Tags:** cc.complexity-theory, reference-request, polynomials

> **Comments:**
> **username_1**: A quick web search reveals many sources, and there are also several monographs I can think of that answer your question. Have you looked at these sources?  
> **username_2**: I think they reduce factoring to PIT. Is there a reverse connection?  

---

## 0 answers

