recently multivariate polynomial factoring has been related to Polynomial Identity Testing / PIT (by Kopparty, Saraf, Shpilka).

where is the complexity of factoring multivariate polynomials over finite fields 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?)

  • 3
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Apr 20 '15 at 4:18
  • $\begingroup$ I think they reduce factoring to PIT. Is there a reverse connection? $\endgroup$ – Turbo Apr 20 '15 at 4:55

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.