Multi-linear formulas for permanent and determinant are of super-polynomial size

ABSTRACT

An arithmetic formula is multilinear if the polynomial computed by each of its subformulas is multilinear. We prove that any multilinear arithmetic formula for the permanent or the determinant of an n × n matrix is of size super-polynomial in n. Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multilinear formulas of constant depth.

REFERENCES

• 1: Scott Aaronson, Multilinear formulas and skepticism of quantum computing, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007378]
• 2: Alon, N., Spencer, J. H., and Erdos, P. 1992. The Probabiliatic Method. Wiley, New York.
• 3: Burgisser, P., Clausen, M., and Shokrollahi, M. A. 1997. Algebraic Complexity Theory. Springer-Verlag, New York.
• 4: Dima Grigoriev , Marek Karpinski, An exponential lower bound for depth 3 arithmetic circuits, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.577-582, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276872]
• 5: Grigoriev, D., and Razborov, A. A. 2000. Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput. 10, 6, 465--487 (Preliminary version in FOCS 1998).
• 6: Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, December 2004 [doi>10.1007/s00037-004-0182-6]
• 7: Kalorkoti, K. 1985. A lower bound for the formula size of rational functions. SIAM J. Comput. 14, 3, 678--687.
• 8: Noam Nisan, Lower bounds for non-commutative computation, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.410-418, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103462]
• 9: Noam Nisan , Avi Wigderson, Lower bounds on arithmetic circuits via partial derivatives, Computational Complexity, v.6 n.3, p.217-234, 1997 [doi>10.1007/BF01294256]
• 10: Raz, R. 2006. Separation of multilinear circuit and formula size. Theory of Comput. 2, 6 (Preliminary version in FOCS 2004, title: Multilinear-NC₁ ≠ Multilinear-NC₂).
• 11: Ran Raz , Amir Shpilka, Deterministic polynomial identity testing in non-commutative models, Computational Complexity, v.14 n.1, p.1-19, April 2005 [doi>10.1007/s00037-005-0188-8]
• 12: Ran Raz , Amir Shpilka , Amir Yehudayoff, A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.438-448, October 21-23, 2007 [doi>10.1109/FOCS.2007.6]
• 13: Ran Raz , Amir Yehudayoff, Lower Bounds and Separations for Constant Depth Multilinear Circuits, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.128-139, June 22-26, 2008 [doi>10.1109/CCC.2008.8]
• 14: Ran Raz , Amir Yehudayoff, Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.273-282, October 25-28, 2008 [doi>10.1109/FOCS.2008.22]
• 15: Schnorr, C. P. 1976. A lower bound on the number of additions in monotone computations. Theoret. Comput. Sci. 2, 3, 305--315.
• 16: Shamir, E., and Snir, M. 1980. On the depth complexity of formulas. Math. Syst. Theory 13, 301--322.
• 17: Amir Shpilka , Avi Wigderson, Depth-3 arithmetic circuits over fields of characteristic zero, Computational Complexity, v.10 n.1, p.1-27, 2001 [doi>10.1007/PL00001609]
• 18: Valiant, L. G. 1980. Negation can be exponentially powerful. Theoret. Comput. Sci. 12, 303--314.
• 19: Leslie G. Valiant, Why is Boolean complexity theory difficult?, Poceedings of the London Mathematical Society symposium on Boolean function complexity, p.84-94, December 1992, London, United Kingdom
• 20: Joachim Von Zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation, v.4 n.2, p.137-172, Oct. 1987 [doi>10.1016/S0747-7171(87)80063-9]
• 21: Joachim von zur Gathen, Algebraic complexity theory, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
algebraic complexity, arithmetic formulas, circuit complexity, lower bounds