Algebraic Complexity Classes - Perspectives in Computational Complexity - page 71

References
[ABKPM09] E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, P.B. Miltersen, On the complexity
of numerical analysis. SIAM J. Comput. 38 (5) 1987-2006 (2009)
[AJMV98a] E. Allender, J. Jiao, M. Mahajan, V. Vinay, Non-commutative arithmetic circuits:
depth reduction and size lower bounds. Theoret. Comput. Sci. 209 , 47-86 (1998)
[AJMV98b] E. Allender, J. Jiao, M. Mahajan, V. Vinay, Non-commutative arithmetic circuits:
Depth reduction and size lower bounds. Theor. Comput. Sci. 209 (1-2) 47-86 (1998)
[AV08] M. Agrawal, V. Vinay, Arithmetic circuits: a chasm at depth four, in FOCS , pp. 67-75
(2008). See also ECCC TR15-062, 2008
[AW11] E. Allender, F. Wang, On the power of algebraic branching programs of width two.
ICALP 1 , 736-747 (2011)
[Bar89] D.A. Barrington, Bounded-width polynomial size branching programs recognize
exactly those languages in NC 1 . J. Comput. Syst. Sci. 38 , 150-164 (1989)
[BCS97] P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic Complexity Theory (Springer,
Berlin, 1997)
[BK09] I. Briquel, P. Koiran, A dichotomy theorem for polynomial evaluation, in MFCS , pp.
187-198 (2009)
[BKM11] I. Briquel, P. Koiran, K. Meer, On the expressive power of cnf formulas of bounded
tree- and clique-width. Discrete Appl. Math. 159 (1), 1-14 (2011)
[Blä13] M. Bläser. Noncommutativity makes determinants hard, in Proceedings of ICALP ,
vol. 7965 of Lecture Notes in Computer Science, pp. 172-183, Springer, ECCC TR
2012-142 (2013)
[BOC92] M. Ben-Or, R. Cleve, Computing algebraic formulas using a constant number of
registers. SIAM J. Comput. 21 , 54-58 (1992)
[Bod98] H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth. Theor.
Comput. Sci. 209 (12) 1-45 (1998)
[Bre74] R.P. Brent, The parallel evaluation of general arithmetic expressions. J. ACM 21 ,
201-206 (1974)
[Bür00a] P. Bürgisser, Completeness and Reduction in Algebraic Complexity Theory , vol. 7 of
Algorithms and Computation in Mathematics (Springer, Berlin, 2000)
[Bür00b] P. Bürgisser, Cook's versus Valiant's hypothesis. Theor. Comput. Sci. 235 (1), 71-88
(2000)
[Bür09] P. Bürgisser, On defining integers and proving arithmetic circuit lower bounds. Com-
put. Complex. 18 (1), 81-103 (2009)
[Cai90] J.-Y. Cai, A note on the determinant and permanent problem. Inf. Comput. 84 (1),
119-127 (1990)
[CCL10] J.-Y. Cai, X. Chen, D. Li, Quadratic lower bound for permanent versus determinant
in any characteristic. Comput. Complex. 19 (1), 37-56 (2010)
[CDM13] F. Capelli, A. Durand, S. Mengel, The arithmetic complexity of tensor contractions,
in STACS , vol. 20 of LIPIcs, pp. 365-376 (2013)
[Che04] Q. Cheng, On the ultimate complexity of factorials. Theor. Comput. Sci. 326 (1-3),
419-429 (2004)
[Csa76] L. Csanky, Fast parallel inversion algorithm. SIAM J. Comput. 5 , 818-823 (1976)
[Dam91] C. Damm, DET= L #L . Technical Report Informatik-Preprint 8, Fachbereich Infor-
matik der Humboldt-Universität zu Berlin (1991)
[DM11] A. Durand, S. Mengel, On polynomials defined by acyclic conjunctive queries and
weighted counting problems. CoRR abs/1110.4201 (2011)
[DMPY12] Z. Dvir, G. Malod, S. Perifel, A. Yehudayoff, Separating multilinear branching pro-
grams and formulas, in STOC , pp. 615-624 (2012)
[dMS96] W. de Melo, B.F. Svaiter, The cost of computing integers. Proc. Am. Math. Soc.
124 (5), 1377-1378 (1996)