On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree

by Neeraj Kayal, Chandan Saha, and Sébastien Tavenas

Theory of Computing, Volume 14(16), pp. 1-46, 2018

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]   Noga Alon and Joel Spencer: The Probabilistic Method. Wiley Online Library, 2010. [doi:10.1002/9780470277331]

[3]   Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi: Algebraic Complexity Theory. Springer, 1997. [doi:10.1007/978-3-662-03338-8]

[4]   Suryajith Chillara and Partha Mukhopadhyay: Depth-4 lower bounds, determinantal complexity: A unified approach. In Proc. 31st Symp. Theoretical Aspects of Comp. Sci. (STACS’14), pp. 239–250. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014. [doi:10.4230/LIPIcs.STACS.2014.239, arXiv:1308.1640]

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

[6]   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]

[7]   Dima Grigoriev and Marek Karpinski: An exponential lower bound for depth 3 arithmetic circuits. In Proc. 30th STOC, pp. 577–582. ACM Press, 1998. [doi:10.1145/276698.276872]

[8]    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]

[9]   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]

[10]   Pavel Hrubeš and Amir Yehudayoff: Homogeneous formulas and symmetric polynomials. Comput. Complexity, 20(3):559–578, 2011. [doi:10.1007/s00037-011-0007-3, arXiv:0907.2621]

[11]   Laurent Hyafil: On the parallel evaluation of multivariate polynomials. SIAM J. Comput., 8(2):120–123, 1979. Preliminary version in STOC’78. [doi:10.1137/0208010]

[12]   Neeraj Kayal: An Exponential Lower Bound for the Sum of Powers of Bounded Degree Polynomials. Electron. Colloq. on Comput. Complexity (ECCC), 19:81, 2012.

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

[14]   Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan: An exponential lower bound for homogeneous depth four arithmetic formulas. SIAM J. Comput., 46(1):307–335, 2017. Preliminary version in FOCS’14. [doi:10.1137/151002423]

[15]   Neeraj Kayal, Vineet Nair, and Chandan Saha: Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In Proc. 33rd Symp. Theoretical Aspects of Comp. Sci. (STACS’16), pp. 46:1–46:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.STACS.2016.46]

[16]   Neeraj Kayal and Chandan Saha: Lower Bounds for Sums of Products of Low arity Polynomials. Electron. Colloq. on Comput. Complexity (ECCC), 22:73, 2015.

[17]   Neeraj Kayal and Chandan Saha: Lower bounds for depth-three arithmetic circuits with small bottom fanin. Comput. Complexity, 25(2):419–454, 2016. Preliminary version in CCC’15. [doi:10.1007/s00037-016-0132-0]

[18]   Neeraj Kayal and Chandan Saha: Multi-k-ic depth three circuit lower bound. Theory Comput. Syst., 61(4):1237–1251, 2017. Preliminary version in STACS’15. [doi:10.1007/s00224-016-9742-9]

[19]   Neeraj Kayal, Chandan Saha, and Sébastien Tavenas: On the size of homogeneous and of depth four formulas with low individual degree. In Proc. 48th STOC, pp. 626–632. ACM Press, 2016. [doi:10.1145/2897518.2897550]

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

[22]   Mrinal Kumar and Shubhangi Saraf: The limits of depth reduction for arithmetic formulas: It’s all about the top fan-in. SIAM J. Comput., 44(6):1601–1625, 2015. Preliminary version in STOC’14. [doi:10.1137/140999220, arXiv:1311.6716]

[23]   Mrinal Kumar and Shubhangi Saraf: Sums of products of polynomials in few variables: Lower bounds and Polynomial Identity Testing. In Proc. 31st Conf. on Computational Complexity (CCC’16), pp. 35:1–35:29. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.35, arXiv:1504.06213]

[24]   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]

[25]   Mrinal Kumar and Shubhangi Saraf: Arithmetic circuits with locally low algebraic rank. 2018. [arXiv:1806.06097]

[26]   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]

[27]   Rafael Oliveira: Factors of low individual degree polynomials. Comput. Complexity, 25(2):507–561, 2016. Preliminary version in CCC’15. [doi:10.1007/s00037-016-0130-2]

[28]   Ran Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2):8:1–8:17, 2009. Preliminary version in STOC’04. [doi:10.1145/1502793.1502797]

[29]   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]

[30]   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]

[31]   Ramprasad Saptharishi: A survey of lower bounds in arithmetic circuit complexity, 2016. Available at GitHub.

[32]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends, 5(3–4):207–388, 2010. [doi:10.1561/0400000039]

[33]   Emanuel Sperner: Ein satz über untermengen einer endlichen menge. Mathematische Zeitschrift, 27(1):544–548, 1928. [doi:10.1007/BF01171114]

[34]   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]

[35]   Leslie G. Valiant: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM Press, 1979. [doi:10.1145/800135.804419]

[36]   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]