The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials

by Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan

Theory of Computing, Volume 13(9), pp. 1-34, 2017

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: Perturbed identity matrices have high rank: Proof and applications. Combin. Probab. Comput., 18(1-2):3–15, 2009. [doi:10.1017/S0963548307008917]

[3]   László Babai and Peter Frankl: Linear Algebra Methods in Combinatorics. 1992. Book manuscript, University of Chicago.

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

[5]   Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan: The shifted partial derivative complexity of elementary symmetric polynomials. In Proc. 40th Math. Found. Comp. Sci. (MFCS’15), volume 9235 of LNCS, pp. 324–335. Springer, 2015. Preliminary version in ECCC. [doi:10.1007/978-3-662-48054-0_27]

[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]   Peter Frankl: Intersection theorems and modp rank of inclusion matrices. J. Comb. Theory, Ser. A, 54(1):85–94, 1990. [doi:10.1016/0097-3165(90)90007-J]

[8]   Peter Frankl and Richard M. Wilson: Intersection theorems with geometric consequences. Combinatorica, 1(4):357–368, 1981. [doi:10.1007/BF02579457]

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

[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]   Neeraj Kayal: An exponential lower bound for the sum of powers of bounded degree polynomials. Elect. Colloq. Comput. Complexity (ECCC), 19(81), 2012. ECCC.

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

[13]   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. Preliminary version in ECCC. [doi:10.1145/2591796.2591847]

[14]   Peter Keevash and Benny Sudakov: Set systems with restricted cross-intersections and the minimum rank of inclusion matrices. SIAM J. Discrete Math., 18(4):713–727, 2005. [doi:10.1137/S0895480103434634]

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

[16]   Mrinal Kumar and Shubhangi Saraf: On the power of homogeneous depth 4 arithmetic circuits. In Proc. 55th FOCS, pp. 364–373. IEEE Comp. Soc. Press, 2014. Preliminary version in ECCC. [doi:10.1109/FOCS.2014.46, arXiv:1404.1950]

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

[18]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, 1997.

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

[20]   Ran Raz: Separation of multilinear circuit and formula size. Theory of Computing, 2(6):121–135, 2006. [doi:10.4086/toc.2006.v002a006]

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

[22]   Alexander A. Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes of the Acad. Sci. USSR, 41(4):333–338, 1987. [doi:10.1007/BF01137685]

[23]   Amir Shpilka: Affine projections of symmetric polynomials. J. Comput. System Sci., 65(4):639–659, 2002. Preliminary version in CCC’01. [doi:10.1016/S0022-0000(02)00021-1]

[24]   Amir Shpilka and Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complexity, 10(1):1–27, 2001. Preliminary version in CCC’99. [doi:10.1007/PL00001609]

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

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

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

[28]   Richard M. Wilson: A diagonal form for the incidence matrices of t-subsets vs. k-subsets. European J. Combin., 11(6):609–615, 1990. [doi:10.1016/S0195-6698(13)80046-7]