Algebraic Complexity Classes - Perspectives in Computational Complexity - page 73

[Pól13] G. Pólya. Aufgabe 424. Archiv der Mathematik und Physik 3 (20) 271 (1913)
[Rao10] B.V. Raghavendra Rao, A Study of Width Bounded Arithmetic Circuits
and the Complexity of Matroid Isomorphism, Ph.D. thesis. The Institute of

Mathematical Sciences, Chennai, India., 2010. http://www.imsc.res.in/xmlui/

handle/123456789/177
[Raz06] R. Raz, Separation of multilinear circuit and formula size. Theory Comput. 2 (1)
121-135 (2006). preliminary version in FOCS 2004
[Raz09] R. Raz. Multi-linear formulas for permanent and determinant are of super-polynomial
size. J. ACM, 56 (2), (2009). preliminary version in STOC 2004
[Raz10] R. Raz, Elusive functions and lower bounds for arithmetic circuits. Theory Comput.
6 (1), 135-177 (2010)
[RSY08] R. Raz, A. Shpilka, A. Yehudayoff, A lower bound for the size of syntactically
multilinear arithmetic circuits. SIAM J. Comput. 38 (4), 1624-1647 (2008)
[RY08] R. Raz, A. Yehudayoff, Balancing syntactically multilinear arithmetic circuits. Com-
put. Complex. 17 (4), 515-535 (2008)
[RY09] R. Raz, A. Yehudayoff, Lower bounds and separations for constant depth multilinear
circuits. Comput. Complex. 18 (2), 171-207 (2009)
[Rys63] H.J. Ryser, Combinatorial Mathematics (Carus mathematical monographs, Mathe-
matical Association of America, 1963)
[Sav70] J. Walter, Savitch, relationships between nondeterministic and deterministic tape
complexities. J. Comput. Syst. Sci. 4 (2), 177-192 (1970)
[Str73] V. Strassen, Vermeidung von divisionen. J. Reine U. Angew Math 264 , 182-202
(1973)
[SY10] A. Shpilka, A. Yehudayoff, Arithmetic circuits: a survey of recent results and open
questions. Found. Trends Theor. Comput. Sci. 5 (3-4), 207-388 (2010)
[Tav13] S. Tavenas, Improved bounds for reduction to depth 4 and depth 3, in MFCS ,vol.
8087 of Lecture Notes in Computer Science, pp. 813-824 (Springer, Berlin, 2013)
[Tod92] S. Toda, Classes of arithmetic circuits capturing the complexity of computing the
determinant. IEICE Trans. Inf. Syst. E75-D , 116-124 (1992)
[Val79] L.G. Valiant, Completeness classes in algebra, in STOC , pp. 249-261 (1979)
[Val82] L.G. Valiant, Reducibility by algebraic projections, in Logic and Algorithmic: Inter-
national Symposium in honour of Ernst Specker , vol. 30, pp. 365-380. Monograph.
de l'Enseign. Math. (1982)
[Val92] L.G. Valiant, Why is boolean complexity theory difficult? in Boolean Function Com-
plexity , ed. by M.S. Paterson (Cambridge University Press, London Mathematical
Society Lecture Notes Series 169, 1992)
[Ven92] H. Venkateswaran, Circuit definitions of nondeterministic complexity classes. SIAM
J. Comput. 21 , 655-670 (1992)
[Vin91] V. Vinay, Counting auxiliary pushdown automata and semi-unbounded arithmetic
circuits, in Proceedings of 6th Structure in Complexity Theory Conference , pp. 270-
284 (1991)
[Vol99] H. Vollmer, Introduction to Circuit Complexity: A Uniform Approach (Springer, New
York, 1999)
[VSBR83] L.G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff, Fast parallel computation of poly-
nomials using few processors. SIAM J. Comput. 12 (4), 641-644 (1983)
[vzG87] J. von zur Gathen, Permanent and determinant. Linear Algebra Appl. 96 , 87-100
(1987)