Closure Results for Polynomial Factorization

by Chi-Ning Chou, Mrinal Kumar, and Noam Solomon

Theory of Computing, Volume 15(13), pp. 1-34, 2019

Bibliography with links to cited articles

[1]   Manindra Agrawal and V. Vinay: Arithmetic circuits: A chasm at depth four. In Proc. 49th FOCS, pp. 67–75. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.32]

[2]   Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja: Randomized polynomial-time identity testing for noncommutative circuits. Theory of Computing, 15(7):1–36, 2019. [doi:10.4086/toc.2019.v015a007]

[3]   Walter Baur and Volker Strassen: The complexity of partial derivatives. Theoret. Comput. Sci., 22(3):317–330, 1983. [doi:10.1016/0304-3975(83)90110-X]

[4]   Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory. Springer, 2000. [doi:10.1007/978-3-662-04179-6]

[5]   Peter Bürgisser: The complexity of factors of multivariate polynomials. Found. Computational Math., 4(4):369–396, 2004. Preliminary version in FOCS’01. [doi:10.1007/s10208-002-0059-5]

[6]   Richard A. DeMillo and Richard J. Lipton: A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193–195, 1978. [doi:10.1016/0020-0190(78)90067-4]

[7]    Pranjal Dutta, Nitin Saxena, and Amit Sinhababu: Discovering the roots: Uniform closure results for algebraic classes under factoring. In Proc. 50th STOC, pp. 1152–1165. ACM Press, 2018. [doi:10.1145/3188745.3188760, arXiv:1710.03214]

[8]   Zeev Dvir, Amir Shpilka, and Amir Yehudayoff: Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279–1293, 2010. Preliminary version in STOC’08. [doi:10.1137/080735850]

[9]   Michael A. Forbes: Deterministic divisibility testing via shifted partial derivatives. In Proc. 56th FOCS, pp. 451–465. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.35]

[10]   Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan: Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM J. Comput., 44(5):1173–1201, 2015. Preliminary version in STOC’14. [doi:10.1137/140990280]

[11]    Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: Approaching the chasm at depth four. J. ACM, 61(6):33:1–33:16, 2014. Preliminary version in CCC’13. [doi:10.1145/2629541]

[12]   Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064–1079, 2016. Preliminary version in FOCS’13. [doi:10.1137/140957123]

[13]   Valentine Kabanets and Russell Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity, 13(1-2):1–46, 2004. Preliminary version in STOC’03. [doi:10.1007/s00037-004-0182-6]

[14]   Kyriakos Kalorkoti: A lower bound for the formula size of rational functions. SIAM J. Comput., 14(3):678–687, 1985. Preliminary version in ICALP’82. [doi:10.1137/0214050]

[15]   Erich Kaltofen: Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput., 14(2):469–489, 1985. [doi:10.1137/0214035]

[16]   Erich Kaltofen: Uniform closure properties of P-computable functions. In Proc. 18th STOC, pp. 330–337. ACM Press, 1986. [doi:10.1145/12130.12163]

[17]   Erich Kaltofen: Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. In Proc. 19th STOC, pp. 443–452. ACM Press, 1987. [doi:10.1145/28395.28443]

[18]   Erich Kaltofen: Factorization of polynomials given by straight-line programs. In Randomness and Computation, pp. 375–412. JAI Press, 1989.

[19]   Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi: A super-polynomial lower bound for regular arithmetic formulas. In Proc. 46th STOC, pp. 146–153. ACM Press, 2014. [doi:10.1145/2591796.2591847]

[20]   Pascal Koiran: Arithmetic circuits: The chasm at depth four gets wider. Theoret. Comput. Sci., 448:56–65, 2012. [doi:10.1016/j.tcs.2012.03.041, arXiv:1006.4700]

[21]   Mrinal Kumar: A quadratic lower bound for homogeneous algebraic branching programs. Comput. Complexity, 28(3):409–435, 2019. Preliminary version in CCC’17. [doi:10.1007/s00037-019-00186-3]

[22]   Mrinal Kumar and Ramprasad Saptharishi: An exponential lower bound for homogeneous depth-5 circuits over finite fields. In Proc. 32nd Computational Complexity Conf. (CCC’17), volume 79, pp. 31:1–31:30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.31, arXiv:1507.00177]

[23]   Mrinal Kumar and Shubhangi Saraf: On the power of homogeneous depth 4 arithmetic circuits. SIAM J. Comput., 46(1):336–387, 2017. Preliminary version in FOCS’14. [doi:10.1137/140999335, arXiv:1404.1950]

[24]   Rudolf Lidl and Harald Niederreiter: Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, 2nd edition, 1996. [doi:10.1017/CBO9780511525926]

[25]   David E. Muller: Application of boolean algebra to switching circuit design and to error detection. Trans. Inst. Radio Engineers Professional Group on Electronic Computers, EC-3:6–12, 1954. [doi:10.1109/IREPGELC.1954.6499441]

[26]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. Preliminary version in FOCS’88. [doi:10.1007/BF01375474]

[27]   Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci., 49(2):149–167, 1994. Preliminary version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1]

[28]   Noam Nisan and Avi Wigderson: Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity, 6(3):217–234, 1996. Preliminary version in FOCS’95. [doi:10.1007/BF01294256]

[29]   Rafael Oliveira: Factors of low individual degree polynomials. Comput. Complexity, 25(2):507–561, 2016. [doi:10.1007/s00037-016-0130-2]

[30]   Øystein Ore: Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I, 7(15):27, 1922. Polynomial Identity Lemma cited with full proof in [24, Theorem 6.13].

[31]   Ran Raz: Separation of multilinear circuit and formula size. Theory of Computing, 2(6):121–135, 2006. Preliminary version in FOCS’04. [doi:10.4086/toc.2006.v002a006]

[32]   Ran Raz: Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6(7):135–177, 2010. Preliminary version in STOC’08. [doi:10.4086/toc.2010.v006a007]

[33]   Ran Raz: Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):40:1–40:15, 2013. Preliminary version in STOC’10. [doi:10.1145/2535928]

[34]   Ran Raz, Amir Shpilka, and Amir Yehudayoff: A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. Comput., 38(4):1624–1647, 2008. Preliminary version in FOCS’07. [doi:10.1137/070707932]

[35]   Ran Raz and Amir Yehudayoff: Lower bounds and separations for constant depth multilinear circuits. Comput. Complexity, 18(2):171–207, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0270-8]

[36]   Wolfgang M. Schmidt: Equations over Finite Fields: An Elementary Approach. Volume 536 of Lecture Notes in Math. Springer, 1st edition, 1976.

[37]   Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980. Preliminary version in EUROSAM’79. [doi:10.1145/322217.322225]

[38]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Found. and Trends Theor. Comput. Sci., 5:207–388, 2010. [doi:10.1561/0400000039]

[39]   Sébastien Tavenas: Improved bounds for reduction to depth 4 and depth 3. Inform. and Comput., 240:2–11, 2015. Preliminary version in MFCS’13. [doi:10.1016/j.ic.2014.09.004, arXiv:1304.5777]

[40]   Leslie G. Valiant: Reducibility by algebraic projections. In Logic and Algorithmic, volume 28 of L’Enseignement Mathématique, pp. 253–268. 1982.

[41]   Leslie G. Valiant, Sven Skyum, Stuart J. Berkowitz, and Charles Rackoff: Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983. Preliminary version in MFCS’81. [doi:10.1137/0212043]

[42]   Richard E. Zippel: Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Comput. (EUROSAM’79), volume 72 of LNCS, pp. 216–226. Springer, 1979. [doi:10.1007/3-540-09519-5_73]