Factors of Low Individual Degree Polynomials

Author Rafael Oliveira



PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.198.pdf
  • Filesize: 0.54 MB
  • 19 pages

Document Identifiers

Author Details

Rafael Oliveira

Cite AsGet BibTex

Rafael Oliveira. Factors of Low Individual Degree Polynomials. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 198-216, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CCC.2015.198

Abstract

In [Kaltofen, 1989], Kaltofen proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen's work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in [Kopparty/Saraf/Shpilka,CCC'14], and the question of bounding the depth of the circuits computing the factors of a polynomial. We are able to answer these questions in the affirmative for the interesting class of polynomials of bounded individual degrees, which contains polynomials such as the determinant and the permanent. We show that if P(x_1, ..., x_n) is a polynomial with individual degrees bounded by r that can be computed by a formula of size s and depth d, then any factor f(x_1, ..., x_n) of P(x_1, ..., x_n) can be computed by a formula of size poly((rn)^r, s) and depth d+5. This partially answers the question above posed in [Kopparty/Saraf/Shpilka,CCC'14], that asked if this result holds without the exponential dependence on r. Our work generalizes the main factorization theorem from Dvir et al. [Dvir/Shpilka/Yehudayoff,SIAM J. Comp., 2009], who proved it for the special case when the factors are of the form f(x_1, ..., x_n) = x_n - g(x_1, ..., x_n-1). Along the way, we introduce several new technical ideas that could be of independent interest when studying arithmetic circuits (or formulas).
Keywords
  • Arithmetic Circuits
  • Factoring
  • Algebraic Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Benny Chor and Ronald L. Rivest. A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory, 34(5):901-909, 1988. Google Scholar
  2. Z. Dvir, A. Shpilka, and A. Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. on Computing, 39(4):1279-1293, 2009. Google Scholar
  3. J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 1999. Google Scholar
  4. J. Von Zur Gathen and E. Kaltofen. Factoring sparse multivariate polynomials. Journal of Computer and System Sciences, 31(2):265-287, 1985. Google Scholar
  5. V. Guruswami and M. Sudan. Improved decoding of reed-solomon and algebraic-geometry codes. IEEE Trans. Inf. Theor., 45(6):1757-1767, September 2006. Google Scholar
  6. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Google Scholar
  7. E. Kaltofen. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. on computing, 14(2):469-489, 1985. Google Scholar
  8. E. Kaltofen. Factorization of polynomials given by straight-line programs. In S. Micali, editor, Randomness in Computation, volume 5 of Advances in Computing Research, pages 375-412. JAI Press, 1989. Google Scholar
  9. E. Kaltofen. Polynomial factorization: a success story. In ISSAC, pages 3-4, 2003. Google Scholar
  10. Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 169-180, 2014. Google Scholar
  11. A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, 1982. Google Scholar
  12. Hendrik W Lenstra Jr. Finding small degree factors of lacunary polynomials. Number theory in progress, 1:267-276, 1999. Google Scholar
  13. R. Oliveira. Factors of low individual degree polynomials. http://www.cs.princeton.edu/~rmo/papers/small-depth-factors.pdf, 2015.
  14. A. Shpilka and I. Volkovich. On the relation between polynomial identity testing and finding variable disjoint factors. In ICALP (1), pages 408-419, 2010. Google Scholar
  15. A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  16. Madhu Sudan. Decoding of reed solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180-193, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail