Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models

by Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse

Theory of Computing, Volume 19(12), pp. 1-30, 2023

Bibliography with links to cited articles

[1]   Manindra Agrawal: Proving lower bounds via pseudo-random generators. In Proc. 25th Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’05), pp. 92–105. Springer, 2005. [doi:10.1007/11590156_6]

[2]   Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena: Bootstrapping variables in algebraic circuits. Proc. Nat. Acad. Sci. USA, 116(17):8107–8118, 2019. Preliminary version in STOC’18. [doi:10.1073/pnas.1901272116, ECCC:TR18-035]

[3]   Manindra Agrawal, Neeraj Kayal, and Nitin Saxena: PRIMES is in P. Ann. Math., 160(2):781–793, 2004. [doi:10.4007/annals.2004.160.781]

[4]   Erwin H. Bareiss: Sylvester’s identity and multistep integer-preserving Gaussian elimination. Math. Comput., 22(103):565–578, 1968. [doi:10.1090/S0025-5718-1968-0226829-0]

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

[6]   Anurag Bishnoi, Pete L. Clark, Aditya Potukuchi, and John R. Schmitt: On zeros of a polynomial in a finite grid. Combin. Probab. Comput., 27(3):310–333, 2018. [doi:10.1017/S0963548317000566]

[7]   Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory. Volume 7 of Algorithms and Computation in Mathematics. Springer, 2000. [doi:10.1007/978-3-662-04179-6]

[8]   Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin: Hardness amplification for non-commutative arithmetic circuits. In Proc. 33rd Comput. Complexity Conf. (CCC’18), pp. 12:1–16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.12, ECCC:TR18-095]

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

[10]   Jack Edmonds: Systems of distinct representatives and linear algebra. J. Res. Nat. Bureau of Standards (B), 71:241–245, 1967. [doi:10.6028/jres.071b.033]

[11]   Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf: Bipartite perfect matching is in quasi-NC. SIAM J. Comput., 50(3), 2021. Preliminary version in STOC’16. [doi:10.1137/16M1097870, arXiv:1601.06319, ECCC:TR15-177]

[12]   Michael A. Forbes: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. Ph. D. thesis, Massachusetts Institute of Technology, 2014. DSpace@MIT.

[13]   Joshua Grochow: Degree restriction for polynomials in VP, 2013. stackexchange.

[14]   Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon: Derandomization from algebraic hardness. SIAM J. Comput., 51(2):315–335, 2022. Preliminary version in FOCS’19. [doi:10.1137/20M1347395]

[15]   Joos Heintz and Claus-Peter Schnorr: Testing polynomials which are easy to compute (extended abstract). In Proc. 12th STOC, pp. 262–272. ACM Press, 1980. [doi:10.1145/800141.804674]

[16]   Jan P. Hogendijk: Sharaf al-din Ṭusi on the number of positive roots of cubic equations. Historia Mathematica, 16(1):69–85, 1989. [doi:10.1016/0315-0860(89)90099-2]

[17]   Maurice J. Jansen and Rahul Santhanam: Marginal hitting sets imply super-polynomial lower bounds for permanent. In Proc. 3rd Innovations in Theoret. Comp. Sci. Conf. (ITCS’12), pp. 496–506. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012. [doi:10.1145/2090236.2090275, ECCC:TR11-133]

[18]   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, ECCC:TR02-055]

[19]   Erich Kaltofen: Factorization of polynomials given by straight-line programs. In Silvio Micali, editor, Randomness and Computation, pp. 375–412. JAI Press, 1989. DSpace@MIT. Preliminary version in FOCS’85.

[20]   Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse: Near-optimal bootstrapping of hitting sets for algebraic circuits. In Proc. 30th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’19), pp. 639–646. SIAM, 2019. [doi:10.1137/1.9781611975482.40]

[21]   Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1990. Preliminary version in FOCS’90. [doi:10.1145/146585.146605]

[22]   Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani: Matching is as easy as matrix inversion. Combinatorica, 7(1):105–113, 1987. Preliminary version in STOC’87. [doi:10.1007/BF02579206]

[23]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. [doi:10.1007/BF01375474]

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

[25]   Øystein Ore: Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922.

[26]   Ramprasad Saptharishi: A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015.

[27]   Alexander Schrijver: Theory of Linear and Integer Programming. Wiley–Interscience, 1986. Wiley.

[28]   Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. [doi:10.1145/322217.322225]

[29]   Adi Shamir: IP=PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90. [doi:10.1145/146585.146609]

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

[31]   Amit Sinhababu and Thomas Thierauf: Factorization of polynomials given by arithmetic branching programs. Comput. Complexity, 30(2):15:1–47, 2021. Preliminary version in CCC’20. [doi:10.1007/s00037-021-00215-0, ECCC:TR20-077]

[32]   Ola Svensson and Jakub Tarnawski: The matching problem in general graphs is in quasi-NC. In Proc. 58th FOCS, pp. 696–707. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.70, arXiv:1704.01929, ECCC:TR17-059]

[33]   Richard Zippel: Probabilistic algorithms for sparse polynomials. In Proc. Internat. Symp. Symbolic and Algebraic Manipulation (EUROSAM’79), pp. 216–226. Springer, 1979. [doi:10.1007/3-540-09519-5_73]