Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field

by Zeyu Guo, Nitin Saxena, and Amit Sinhababu

Theory of Computing, Volume 15(16), pp. 1-30, 2019

Bibliography with links to cited articles

[1]   Leonard M. Adleman and Hendrik W. Lenstra: Finding irreducible polynomials over finite fields. In Proc. 18th STOC, pp. 350–355. ACM Press, 1986. [doi:10.1145/12130.12166]

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

[3]   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’12. [doi:10.1137/130910725, arXiv:1111.0582]

[4]   Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090]

[5]   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. Preliminary version in STOC’17. [doi:10.4086/toc.2019.v015a007]

[6]   László Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM Press, 1985. [doi:10.1145/22145.22192]

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

[8]   Elmar Böhler, Christian Glaßer, and Daniel Meister: Error-bounded probabilistic computations between MA and AM. J. Comput. System Sci., 72(6):1043–1076, 2006. Preliminary version in MFCS’03. [doi:10.1016/j.jcss.2006.05.001]

[9]   Allan Borodin, Joachim von zur Gathem, and John Hopcroft: Fast parallel matrix and GCD computations. Inf. Control, 52(3):241–256, 1982. Preliminary version in FOCS’82. [doi:10.1016/S0019-9958(82)90766-5]

[10]   Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam: On algebraic branching programs of small width. J. ACM, 65(5):32:1–32:29, 2018. Preliminary version in CCC’17. [doi:10.1145/3209663, arXiv:1702.05328]

[11]   Peter Bürgisser: The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics, 4(4):369–396, 2004. Preliminary version in FOCS’01. [doi:10.1007/s10208-002-0059-5]

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

[13]   Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson: Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. In Proc. 9th Innovations in Theoretical Computer Science Conf. (ITCS’18), pp. 24:1–24:20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.24, arXiv:1711.08039]

[14]   Chi-Ning Chou, Mrinal Kumar, and Noam Solomon: Closure results for polynomial factorization. Theory of Computing, 15(13):1–34, 2019. Preliminary version in CCC’18. [doi:10.4086/toc.2019.v015a013]

[15]   Laszlo Csanky: Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976. [doi:10.1137/0205040]

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

[17]   Harm Derksen and Gregor Kemper: Computational Invariant Theory. Springer, 2015. [doi:10.1007/978-3-662-48422-7]

[18]   Zeev Dvir: Extractors for varieties. Comput. Complexity, 21(4):515–572, 2012. Preliminary version in CCC’09. [doi:10.1007/s00037-011-0023-3]

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

[20]   Richard Ehrenborg and Gian-Carlo Rota: Apolarity and canonical forms for homogeneous polynomials. Eur. J. Combinatorics, 14(3):157–181, 1993. [doi:10.1006/eujc.1993.1022]

[21]   Michael A. Forbes and Amir Shpilka: A PSPACE construction of a hitting set for the closure of small algebraic circuits. In Proc. 50th STOC, pp. 1180–1192. ACM Press, 2018. [doi:10.1145/3188745.3188792]

[22]   Shafi Goldwasser and Michael Sipser: Private coins versus public coins in interactive proof systems. In Silvio Micali, editor, Randomness in Computation, volume 5 of Advances in Computing Research, pp. 73–90. JAI Press, 1989. Preliminary version in STOC’86.

[23]   Joshua A. Grochow and Toniann Pitassi: Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. J. ACM, 65(6):37:1–37:59, 2018. Preliminary version in FOCS’14. [doi:10.1145/3230742]

[24]   Zeyu Guo, Nitin Saxena, and Amit Sinhababu: Algebraic dependencies and PSPACE algorithms in approximative complexity. In Proc. 33rd Computational Complexity Conf. (CCC’18), pp. 10:1–10:21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.10, arXiv:1801.09275]

[25]   Joe Harris: Algebraic Geometry: A First Course. Springer, 1992. [doi:10.1007/978-1-4757-2189-8]

[26]   Robin Hartshorne: Algebraic Geometry. Springer, 1977. [doi:10.1007/978-1-4757-3849-0]

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

[28]   Aubrey W. Ingleton: Representation of matroids. Combinatorial Mathematics and its applications, pp. 149–167, 1971.

[29]   Carl Gustav Jacob Jacobi: De Determinantibus functionalibus. Journal für die reine und angewandte Mathematik (Crelles J.), 1841(22):319–359, 1841. [doi:10.1515/crll.1841.22.319]

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

[31]   Neeraj Kayal and Nitin Saxena: Complexity of ring morphism problems. Comput. Complexity, 15(4):342–390, 2006. [doi:10.1007/s00037-007-0219-8]

[32]   Pascal Koiran: Hilbert’s Nullstellensatz is in the polynomial hierarchy. J. Complexity, 12(4):273–286, 1996. [doi:10.1006/jcom.1996.0019]

[33]   János Kollár: Sharp effective Nullstellensatz. J. Amer. Math. Soc., 1(4):963–975, 1988. [doi:10.2307/1990996]

[34]   Mrinal Kumar and Shubhangi Saraf: Arithmetic circuits with locally low algebraic rank. Theory of Computing, 13(6):1–33, 2017. Preliminary version in CCC’16. [doi:10.4086/toc.2017.v013a006, arXiv:1806.06097]

[35]   Joseph M. Landsberg: Tensors: Geometry and Applications. Amer. Math. Soc., 2012. [doi:10.1090/gsm/128]

[36]   François Le Gall: Powers of tensors and fast matrix multiplication. In Proc. 39th Internat. Symp. Symbolic and Algebraic Computation (ISSAC’14), pp. 296–303. ACM Press, 2014. [doi:10.1145/2608628.2608664, arXiv:1401.7714]

[37]   Thomas Lehmkuhl and Thomas Lickteig: On the order of approximation in approximative triadic decompositions of tensors. Theoret. Comput. Sci., 66(1):1–14, 1989. [doi:10.1016/0304-3975(89)90141-2]

[38]   Rudolf Lidl and Harald Niederreiter: Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, 2nd edition, 1996. [doi:10.1017/CBO9780511525926]

[39]   Hideyuki Matsumura: Commutative Algebra. Benjamin-Cummings Pub Co, 1980.

[40]   Ernst W. Mayr and Albert R. Meyer: The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math., 46(3):305–329, 1982. [doi:10.1016/0001-8708(82)90048-2]

[41]   Johannes Mittmann, Nitin Saxena, and Peter Scheiblechner: Algebraic independence in positive characteristic: A p-adic calculus. Trans. Amer. Math. Soc., 366(7):3425–3450, 2014. [doi:10.1090/S0002-9947-2014-06268-5, arXiv:1202.4301]

[42]   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(3):6–12, 1954. [doi:10.1109/IREPGELC.1954.6499441]

[43]   Ketan D. Mulmuley: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica, 7(1):101–104, 1987. Preliminary version in STOC’86. [doi:10.1007/BF02579205]

[44]   Ketan D. Mulmuley: Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma. In Proc. 53rd FOCS, pp. 629–638. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.15]

[45]   Ketan D. Mulmuley: Geometric complexity theory V: Efficient algorithms for Noether normalization. J. Amer. Math. Soc., 30(1):225–309, 2017. Preliminary version in FOCS’12. [doi:10.1090/jams/864, arXiv:1209.5993]

[46]   Øystein Ore: Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I, 7(15):27, 1922. Polynomial Identity Lemma cited with full proof in [38, Theorem 6.13].

[47]   Anurag Pandey, Nitin Saxena, and Amit Sinhababu: Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits. Comput. Complexity, 27(4):617–670, 2018. Preliminary version in MFCS’16. [doi:10.1007/s00037-018-0167-5]

[48]   Oskar Perron: Algebra. I: Die Grundlagen. Walter de Gruyter, 1927.

[49]   Arkadiusz Płoski: Algebraic dependence of polynomials after O. Perron and some applications. In Computational Commutative and Non-Commutative Algebraic Geometry, pp. 167–173. IOS Press, 2005.

[50]   Claudiu Raicu: Secant varieties of Segre–Veronese varieties. Algebra & Number Theory, 6(8):1817–1868, 2012. [doi:10.2140/ant.2012.6.1817]

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

[52]   Nitin Saxena: Progress on polynomial identity testing. Bulletin of the EATCS, 99:49–79, 2009. Online version ECCC TR09-101.

[53]   Nitin Saxena: Progress on polynomial identity testing - II. In Perspectives in Computational Complexity, pp. 131–146. Springer, 2014. [doi:10.1007/978-3-319-05446-9_7, arXiv:1401.0976]

[54]   Marcus Schaefer and Daniel Štefankovič: The complexity of tensor rank. Theory of Computing Systems, 62(5):1161–1174, 2018. [doi:10.1007/s00224-017-9800-y, arXiv:1612.04338]

[55]   Joachim Schmid: On the affine Bezout inequality. manuscripta mathematica, 88(1):225–232, 1995. [doi:10.1007/BF02567819]

[56]   Wolfgang M. Schmidt: Equations over Finite Fields: An Elementary Approach. Volume 536 of Lecture Notes in Math. Springer, 1st edition, 1976. [doi:10.1007/BFb0080437]

[57]   Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. Preliminary version in EUROSAM’79. [doi:10.1145/322217.322225]

[58]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3–4):207–388, Now Publ., 2009. [doi:10.1561/0400000039]

[59]   Ilya Volkovich: Private Communication, 2018.

[60]   Richard E. 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]