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]. |
This file has been generated by bibtex2html 1.74