Non-Commutative Arithmetic Circuits with Division

by Pavel Hrubeš and Avi Wigderson

Theory of Computing, Volume 11(14), pp. 357-393, 2015

Bibliography with links to cited articles

[1]   Bharat Adsul, Suresh Nayak, and K. V. Subrahmanyam: A geometric approach to the Kronecker problem II: Invariants of matrices for simultaneous left-right actions, 2010. Available at

[2]   Shimshon A. Amitsur: Rational identities and applications to algebra and geometry. J. Algebra, 3(3):304–359, 1966. [doi:10.1016/0021-8693(66)90004-4]

[3]   Shimshon A. Amitsur and Jacob Levitzki: Minimal identities for algebras. Proc. Amer. Math. Soc., 1(4):449–463, 1950. [doi:10.1090/S0002-9939-1950-0036751-9]

[4]   Jean Berstel and Christophe Reutenauer: Rational series and their languages. Springer, 1988.

[5]   Andrej Bogdanov and Hoeteck Wee: More on noncommutative polynomial identity testing. In IEEE Conference on Computational Complexity (CCC), pp. 92–99. IEEE Comp. Soc. Press, 2005. [doi:10.1109/CCC.2005.13]

[6]   Richard P. Brent: The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201–206, 1974. [doi:10.1145/321812.321815]

[7]   Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi: Algebraic complexity theory. Volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997. [doi:10.1007/978-3-662-03338-8]

[8]   Paul Moritz Cohn: Free rings and their relations. Academic Press, 1985.

[9]   Paul Moritz Cohn: Skew Fields: Theory of General Division Rings. Volume 57 of Encyclopedia of Mathematics. Cambridge Univ. Press, 1995.

[10]   Paul Moritz Cohn and Christophe Reutenauer: On the construction of the free field. Int. J. Algebra Comput., 9(3-4):307–324, 1999. [doi:10.1142/S0218196799000205]

[11]   David Cox, John Little, and Donal O’Shea: Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer, 2007. [doi:10.1007/978-0-387-35651-8]

[12]   Harm Derksen: Polynomial bounds for rings of invariants. Proc. Amer. Math. Soc., 129(4):955–963, 2001. [doi:10.1090/S0002-9939-00-05698-7]

[13]   Harm Derksen and Gregor Kemper: Computational Invariant Theory. Volume 130 of Encyclopaedia of Math. Sci. Springer, 2002. [doi:10.1007/978-3-662-04958-7]

[14]   Harm Derksen and Jerzy Weyman: Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients. J. Amer. Math. Soc., 13(3):467–479, 2000. [doi:10.1090/S0894-0347-00-00331-3]

[15]   Mátyás Domokos and Alexandr N. Zubkov: Semi-invariants of quivers as determinants. Transform. Groups, 6(1):9–24, 2001. [doi:10.1007/BF01236060]

[16]   Stephen Donkin: Invariants of several matrices. Inventiones Mathematicae, 110(1):389–401, 1992. [doi:10.1007/BF01231338]

[17]   Michael A. Forbes and Amir Shpilka: Explicit Noether normalization for simultaneous conjugation via polynomial identity testing. In Proc. 17th Internat. Workshop on Randomization and Computation (RANDOM’13), pp. 527–542, 2013. [doi:10.1007/978-3-642-40328-6_37, arXiv:1303.0084]

[18]   Edward Formanek: Invariants and the ring of generic matrices. J. Algebra, 89(1):178–223, 1984. [doi:10.1016/0021-8693(84)90240-0]

[19]   Marc Fortin and Christophe Reutenauer: Commutative/non-commuative rank of linear matrices and subspaces of matrices of low rank. Séminaire Lotharingien de Combinatoire, 52, 2004. Available at EUDML.

[20]   Peter Gabriel: Unzerlegbare Darstellungen I. Manuscripta Mathematica, 6(1):71–103, 1972. [doi:10.1007/BF01298413]

[21]   Israel Moiseevich Gelfand, Sergei Gelfand, Vladimir S. Retakh, and Robert Lee Wilson: Quasideterminants. Adv. Math., 193(1):56–141, 2005. [doi:10.1016/j.aim.2004.03.018, arXiv:math/0208146]

[22]   Israel Moiseevich Gelfand and Vladimir S. Retakh: Determinants of matrices over noncommutative rings. Funct. Anal. Appl., 25(2):91–102, 1991. [doi:10.1007/BF01079588]

[23]   Israel Moiseevich Gelfand and Vladimir S. Retakh: A theory of noncommutative determinants and characteristic functions of graphs. Funct. Anal. Appl., 26(4), 1992. [doi:10.1007/BF01075044]

[24]   David Hilbert: Über die vollen Invariantensysteme. Math. Ann., 42(3):313–373, 1893. [doi:10.1007/BF01444162]

[25]   Pavel Hrubeš and Avi Wigderson: Non-commutative circuits with division. In Proc. 5th Conf. Innovations in Theoret. Comp. Sci. (ITCS’14), pp. 49–66, 2014. [doi:10.1145/2554797.2554805]

[26]   Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff: Relationless completeness and separations. In IEEE Conference on Computational Complexity (CCC), pp. 280–290, 2010. Preliminary version in ECCC. [doi:10.1109/CCC.2010.34]

[27]   Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff: Non-commutative circuits and the sum of squares problem. J. Amer. Math. Soc., 24(3):871–898, 2011. Preliminary versions in ECCC and STOC’10. [doi:10.1090/S0894-0347-2011-00694-2]

[28]   Pavel Hrubeš and Amir Yehudayoff: Arithmetic complexity in ring extensions. Theory of Computing, 7(8):119–129, 2011. [doi:10.4086/toc.2011.v007a008]

[29]   Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam: Non-commutative Edmonds’ problem and matrix semi-invariants. CoRR, 2015. [arXiv:1508.00690]

[30]   Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam: On generating the ring of matrix semi-invariants. CoRR, 2015. [arXiv:1508.01554]

[31]   Dmitry Kaliuzhnyi-Verbovetskyi and Victor Vinnikov: Noncommutative rational functions, their difference-differential calculus and realizations. Multidim. Systems and Sig. Proc., 23(1):49–77, 2012. [doi:10.1007/s11045-010-0122-3, arXiv:1003.0695]

[32]   Dmitry S. Kaliuzhnyi-Verbovetskyi and Victor Vinnikov: Singularities of noncommutative rational functions and minimal factorizations. Lin. Alg. Appl., 430(4):869–889, 2009. [doi:10.1016/j.laa.2008.08.027]

[33]   Hanspeter Kraft and Claudio Procesi: Classical Invariant Theory, a Primer. 1996. Available at

[34]   Tsiu-Kwen Lee and Yiqiang Zhou: Right ideals generated by an idempotent of finite rank. Lin. Alg. and Appl., 431(11):2118–2126, 2009. [doi:10.1016/j.laa.2009.07.005]

[35]   Peter Malcolmson: A prime matrix ideal yields a skew field. J. of the London Math. Soc., 18(2):221–233, 1978. [doi:10.1112/jlms/s2-18.2.221]

[36]   Ketan D. Mulmuley: On P vs. NP and geometric complexity theory. J. ACM, 58(2):5:1–5:26, 2011. [doi:10.1145/1944345.1944346]

[37]   Ketan D. Mulmuley: The GCT program toward the P vs. NP problem. Com. of the ACM, 55(6):98–107, 2012. [doi:10.1145/2184319.2184341]

[38]   Ketan D. Mulmuley: Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma. CoRR, p. 60pp, 2012. Extended Abstract in FOCS’12. [arXiv:1209.5993]

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

[40]   Claudio Procesi: The invariant theory of n × n matrices. Adv. Math., 19(3):306–381, 1976. [doi:10.1016/0001-8708(76)90027-X]

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

[42]   Yuri Ptirimovich Razmyslov: Trace identities of full matrix algebras over a field of characteristic zero. Izv. Akad. Nauk SSSR Ser. Mat., 8(4):727–760, 1974. [doi:10.1070/IM1974v008n04ABEH002126]

[43]   Christophe Reutenauer: Inversion height in free fields. Selecta Mathematica, 2(1):93–109, 1996. [doi:10.1007/BF01587940]

[44]   Louis Halle Rowen: Polynomial identities in ring theory. Volume 84. Academic Press, 1980.

[45]   Aidan Schofield and Michel Van den Bergh: Semi-invariants of quivers for arbitrary dimension vectors. Indag. Math, 12(1):125–138, 2001. [doi:10.1016/S0019-3577(01)80010-0, arXiv:math/9907174]

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

[47]   Volker Strassen: Gaussian elimination is not optimal. Numer. Math., 13(4):354–356, 1969. [doi:10.1007/BF02165411]

[48]   Volker Strassen: Vermeidung von Divisionen. J. of Reine Angew. Math., 1973(264):182–202, 1973. [doi:10.1515/crll.1973.264.184]

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