Polynomial factorization is a central problem in computational algebra and algebraic complexity, with connections to many areas in theoretical computer science. Even for the case of sparse multivariate polynomials there is a lot we do not understand- we only know subexponential time deterministic factoring algorithms for sparse polynomials by the recent work of Bhattacharjee, Kumar, Rai, Ramprasad and Saraf. In the case where the input sparse polynomial has constant individual degree, we know how to factor deterministically in quasipolynomial time by the work of Bharagava, Saraf and Volkovich and a recent improvement by Chuyoon and Shpilka.
In this work we give a deterministic polynomial time algorithm that takes as input a sparse polynomial of constant individual degree and outputs a list of circuits such that every factor of the input is in the list. One caveat is that the list might contain additional spurious circuits that are not factors.
We also give a quasipolynomial time deterministic algorithm that takes as input a general sparse polynomial and outputs a list of circuits such that every factor of the input of constant individual degree is in the list. Again the list might contain additional spurious circuits. A consequence of our algorithm is a new upper bound on the total number of bounded individual degree factors of a sparse polynomial.
This is based on joint work with Somnath Bhattacharjee (U of T), Shanthanu S. Rai (TIFR) and Shubhangi Saraf (U of T).
Bio: Rishabh Kothary is a second year PhD student at University of Toronto being advised by Swastik Kopparty and Shubhangi Saraf. He is interested in coding theory and algebraic complexity.
