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]