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]