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].