Arithmetic Circuits with Locally Low Algebraic Rank

by Mrinal Kumar and Shubhangi Saraf

Theory of Computing, Volume 13(6), pp. 1-33, 2017

Bibliography with links to cited articles

[1]   Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena: Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits. SIAM J. Comput., 45(4):1533–1562, 2016. Preliminary version in STOC 2012. [doi:10.1137/130910725, arXiv:1111.0582]

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

[3]   Malte Beecken, Johannes Mittmann, and Nitin Saxena: Algebraic independence and blackbox identity testing. Inform. and Comput., 222:2–19, 2013. Preliminary version in ICALP’11. [doi:10.1016/j.ic.2012.10.004, arXiv:1102.2789]

[4]   Xi Chen, Neeraj Kayal, and Avi Wigderson: Partial derivatives in arithmetic complexity and beyond. Found. and Trends in Theoret. Comput. Sci., 6(1-2):1–138, 2011. [doi:10.1561/0400000043]

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

[6]   Zeev Dvir, Ariel Gabizon, and Avi Wigderson: Extractors and rank extractors for polynomial sources. Comput. Complexity, 18(1):1–58, 2009. Preliminary version in FOCS’07. [doi:10.1007/s00037-009-0258-4]

[7]   Zeev Dvir and Amir Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5):1404–1434, 2007. Preliminary version in STOC’05. [doi:10.1137/05063605X]

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

[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]   Michael A. Forbes and Amir Shpilka: Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In Proc. 54th FOCS, pp. 243–252. IEEE Comp. Soc. Press, 2013. Available at ECCC. [doi:10.1109/FOCS.2013.34, arXiv:1209.2408]

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

[12]   Dima Grigoriev and Alexander A. Razborov: Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput., 10(6):465–487, 2000. Preliminary version in FOCS’98. [doi:10.1007/s002009900021]

[13]   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 versions in CCC’13 and ECCC. [doi:10.1145/2629541]

[14]   Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich: Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM J. Comput., 42(6):2114–2131, 2013. Preliminary versions in STOC’10 and ECCC. [doi:10.1137/110824516]

[15]   Zohar Shay Karnin and Amir Shpilka: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333–364, 2011. Preliminary version in CCC’08. [doi:10.1007/s00493-011-2537-3]

[16]   Neeraj Kayal: The complexity of the annihilating polynomial. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 184–193. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.37]

[17]   Neeraj Kayal: An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloq. on Comput. Complexity (ECCC), (81):1–5, 2012. Available at ECCC.

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

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

[20]   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. Available at ECCC. [doi:10.1145/2591796.2591847]

[21]   Neeraj Kayal, Chandan Saha, and S├ębastien Tavenas: An almost cubic lower bound for depth three arithmetic circuits. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp. 33:1–33:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. Available at ECCC. [doi:10.4230/LIPIcs.ICALP.2016.33]

[22]   Neeraj Kayal and Shubhangi Saraf: Blackbox polynomial identity testing for depth 3 circuits. In Proc. 50th FOCS, pp. 198–207. IEEE Comp. Soc. Press, 2009. Available at ECCC. [doi:10.1109/FOCS.2009.67]

[23]   Neeraj Kayal and Nitin Saxena: Polynomial identity testing for depth 3 circuits. Comput. Complexity, 16(2):115–138, 2007. Preliminary version in CCC 2016. [doi:10.1007/s00037-007-0226-9]

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

[25]   Mrinal Kumar and Ramprasad Saptharishi: An exponential lower bound for homogeneous depth-5 circuits over finite fields. Electron. Colloq. on Comput. Complexity (ECCC), (109):1–36, 2015. Available at ECCC. [arXiv:1507.00177]

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

[27]   Mrinal Kumar and Shubhangi Saraf: Arithmetic circuits with locally low algebraic rank. In Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), pp. 34:1–34:27. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.34]

[28]   Mrinal Kumar and Shubhangi Saraf: Sums of products of polynomials in few variables: lower bounds and polynomial identity testing. In Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), pp. 35:1–35:29. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. Available at ECCC. [doi:10.4230/LIPIcs.CCC.2016.35, arXiv:1504.06213]

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

[30]   Rafael Oliveira, Amir Shpilka, and Ben Lee Volk: Subexponential size hitting sets for bounded depth multilinear formulas. Comput. Complexity, 25(2):455–505, 2016. Preliminary versions in ECCC and 10.4230/LIPIcs.CCC.2015.304CCC 2015. [doi:10.1007/s00037-016-0131-1, arXiv:1411.7492]

[31]   James G. Oxley: Matroid Theory. Oxford Univ. Press, 2006.

[32]   Anurag Pandey, Nitin Saxena, and Amit Sinhababu: Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits. In 41st Internat. Symp. Mathemat. Found. Comput. Sci. (MFCS’16), pp. 74:1–74:15, 2016. [doi:10.4230/LIPIcs.MFCS.2016.74]

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

[34]   Ramprasad Saptharishi: Recent progress on arithmetic circuit lower bounds. Bull. EATCS, (114), 2014.

[35]   Ramprasad Saptharishi: A survey of lower bounds in arithmetic circuit complexity, 2014. Available at author’s GitHub.

[36]   Shubhangi Saraf and Ilya Volkovich: Black-box identity testing of depth-4 multilinear circuits. In Proc. 43rd STOC, pp. 421–430. ACM Press, 2011. Available at ECCC. [doi:10.1145/1993636.1993693]

[37]   Nitin Saxena and C. Seshadhri: From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for deph-3 circuits. In Proc. 51st FOCS, pp. 21–29. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.9]

[38]   Nitin Saxena and C. Seshadhri: Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn’t matter. SIAM J. Comput., 41(5):1285–1298, 2012. Preliminary version in STOC’11. [doi:10.1137/10848232]

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

[40]   Amir Shpilka and Ilya Volkovich: Read-once polynomial identity testing. Comput. Complexity, 24(3):477–532, 2015. Preliminary version in RANDOM’09. [doi:10.1007/s00037-015-0105-8]

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

[42]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Found. and Trends in Theoret. Comput. Sci., 5(3-4):207–388, 2010. [doi:10.1561/0400000039]

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

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