Randomized Polynomial-Time Identity Testing for Noncommutative Circuits

by Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja

Theory of Computing, Volume 15(7), pp. 1-36, 2019

Bibliography with links to cited articles

[1]   Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena: Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669–697, 2015. [doi:10.1137/140975103, arXiv:1406.7535]

[2]   Noga Alon and Zoltán Füredi: Covering the cube by affine hyperplanes. Eur. J. Comb., 14:79–83, 1993. [doi:10.1006/eujc.1993.1011]

[3]   Avraham Shimshon Amitsur and Jacob Levitzki: Minimal identities for algebras. Proc. Amer. Math. Soc., 1:449–463, 1950. [doi:10.2307/2032312]

[4]   Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja: Randomized polynomial time identity testing for noncommutative circuits. In Proc. 49th STOC, pp. 831–841. ACM Press, 2017. [doi:10.1145/3055399.3055442]

[5]   Vikraman Arvind, Pushkar S. Joglekar, and Gaurav Rattan: On the complexity of noncommutative polynomial factorization. Inform. and Comput., 262(1):22–39, 2018. Preliminary version in MFCS’15. [doi:10.1016/j.ic.2018.05.009, arXiv:1501.00671]

[6]   Vikraman Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan: New results on noncommutative and commutative polynomial identity testing. Comput. Complexity, 19(4):521–558, 2010. Preliminary version in CCC’08. [doi:10.1007/s00037-010-0299-8, arXiv:0801.0514]

[7]   Anurag Bishnoi, Pete L. Clark, Aditya Potukuchi, and John Schmitt: On zeros of a polynomial in a finite grid. Combinatorics, Probability and Computing, 27(3):310–333, 08 2018. [doi:10.1017/S0963548317000566, arXiv:1508.06020]

[8]   Andrej Bogdanov and Hoeteck Wee: More on noncommutative polynomial identity testing. In Proc. 20th IEEE Conf. on Computational Complexity (CCC’05), pp. 92–99. IEEE Comp. Soc. Press, 2005. [doi:10.1109/CCC.2005.13]

[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]   Zeev Dvir and Amir Shpilka: Locally decodable codes with two 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]

[11]   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. [doi:10.1109/FOCS.2013.34, arXiv:1209.2408]

[12]   Laurent Hyafil: The power of commutativity. In Proc. 18th FOCS, pp. 171–174. IEEE Comp. Soc. Press, 1977. [doi:10.1109/SFCS.1977.31]

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

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

[15]   Richard J. Lipton: The curious history of the Schwartz–Zippel Lemma. https://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/, 2009.

[16]   Markus Lohrey: Equality testing of compressed strings. In Proc. 10th Int. Conf. on Combinatorics on Words (WORDS’15), pp. 14–26. Springer, 2015. [doi:10.1007/978-3-319-23660-5_2]

[17]   Kurt Mehlhorn, R. Sundar, and Christian Uhrig: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica, 17(2):183–198, 1997. Preliminary version in SODA’94. [doi:10.1007/BF02522825]

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

[19]   Noam Nisan: Lower bounds for non-commutative computation (extended abstract). In Proc. 23rd STOC, pp. 410–418. ACM Press, 1991. [doi:10.1145/103418.103462]

[20]   Øystein Ore: Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I, 7(15):27, 1922.

[21]   Wojciech Plandowski: Testing equivalence of morphisms on context-free languages. In Proc. 2nd Europ. Symp. on Algorithms (ESA’94), pp. 460–470. Springer, 1994. [doi:10.1007/BFb0049431]

[22]   Claudio Procesi: On the theorem of Amitsur–Levitzki. Israel J. Math., 207(1):151–154, 2015. [doi:10.1007/s11856-014-1118-8, arXiv:1308.2421]

[23]   Ran Raz and Amir Shpilka: Deterministic polynomial identity testing in non-commutative models. Comput. Complexity, 14(1):1–19, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0188-8]

[24]   Irving S. Reed: A class of multiple-error-correcting codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory, 4(4):38–49, 1955. [doi:10.1109/TIT.1954.1057465]

[25]   Nitin Saxena and C. Seshadhri: From Sylvester–Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM, 60(5):33:1–33:33, 2013. Preliminary version in FOCS’10. [doi:10.1145/2528403, arXiv:1002.0145]

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

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

[28]   Richard E. Zippel: Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation (EUROSAM’79), volume 72 of LNCS, pp. 216–226. Springer, 1979. [doi:10.1007/3-540-09519-5_73]