Separation of Multilinear Circuit and Formula Size
by Ran Raz
Theory of Computing, Volume 2(6), pp. 121-135, 2006
Bibliography with links to cited articles
[1] S. Aaronson: Multilinear formulas and skepticism of quantum computing. In Proc. 36th ACM Symp. on Theory of Computation, pp. 118–127, 2004. [STOC:1007352.1007378, arXiv:quant-ph/0311039].
[2] P. Bürgisser, M. Clausen, and M. A. Shokrollahi: Algebraic Complexity Theory. Springer-Verlag New York, Inc., 1997.
[3] L. Hyafil: On the parallel evaluation of multivariate polynomials. SIAM Journal on Computing, 8(2):120–123, 1979. [SICOMP:08/0208010].
[4] N. Nisan: Lower bounds for non-commutative computation. In Proc. 23rd ACM Symp. on Theory of Computing, pp. 410–418, 1991. [STOC:103418.103462].
[5] N. Nisan and A. Wigderson: Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217–234, 1996. Preliminary version in FOCS 1995. [CC:v34728p847187762, FOCS:10.1109/SFCS.1995.492458].
[6] R. Raz: Multilinear-NC1 Multilinear-NC2. In Proc. 45th Symp. Found. Computer Science, pp. 344–351, 2004. [FOCS:10.1109/FOCS.2004.42].
[7] R. Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size. Journal of the ACM, to appear. Preliminary version in STOC 2004. [STOC:1007352.1007353].
[8] L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff: Fast parallel computation of polynomials using few processors. SIAM Journal on Computing, 12(4):641–644, 1983. [SICOMP:12/0212043].
[9] J. von zur Gathen: Algebraic complexity theory. Ann. Rev. Computer Science, 3:317–347, 1988. [ARCS:10.1146/annurev.cs.03.060188.001533].