Zeev Dvir
ABSTRACT
This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of multilinear ABPs to that of multilinear arithmetic formulas, and prove a tight super-polynomial separation between the two models. Specifically, we describe an explicit n-variate polynomial F that is computed by a linear-size multilinear ABP but every multilinear formula computing F must be of size nΩ(log n).
Supplemental Material
- S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Proc. Letters 18, pages 147--150, 1984. Google Scholar
Digital Library
- P. Bürgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2000.Google Scholar
- . J. Jansen. Lower bounds for syntactically multilinear algebraic branching programs. In Mathematical Foundations of Computer Science 2008, pages 407--418, volume 5162 of LNCS. Springer, 2008. Google ScholarDigital Library
- M. Mahajan and V. Vinay. Determinant: Combinatorics, Algorithms, and Complexity. Chicago J. Theor. Comput. Sci., 1997.Google Scholar
- G. Malod and N. Portier. Characterizing Valiant's algebraic complexity classes. Journal of Complexity 24 (1), pages 16--38, 2008. Google ScholarDigital Library
- N. Nisan and A. Wigderson. Lower bound on arithmetic circuits via partial derivatives. Computational Complexity 6, pages 217--234, 1996. Google ScholarDigital Library
- R. Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. In Proceedings of the 36th Annual STOC, pages 633--641, 2004. Google ScholarDigital Library
- R. Raz. Multilinear $NC_1 \neq$ Multilinear $NC_2$. In Proceedings of the 45th Annual FOCS, pages 344--351, 2004. Google ScholarDigital Library
- R. Raz, A. Shpilka, and A. Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. on Computing 38 (4), pages 1624--1647, 2008. Google ScholarDigital Library
- R. Raz and A. Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity 17 (4), pages 515--535, 2008. Google ScholarDigital Library
- R. Raz and A. Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity 18 (2), pages 171--207, 2009.Google ScholarCross Ref
- P. A. Samuelson. A method for determining explicitly the coefficients of the characteristic equation. Ann. Math. Statist. 13, pages 424--429, 1942.Google ScholarCross Ref
- A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5, pages 207--388, 2010. Google ScholarDigital Library
- S. Toda. Classes of Arithmetic Circuits Capturing the Complexity of Computing the Determinant. IEICE Transactions on Information and Systems, E75-D:116--124, 1992.Google Scholar
- L. G. Valiant. Completeness classes in algebra. In Proceedings of the 11th Annual STOC,pages 249--261, 1979. Google ScholarDigital Library
Index Terms
- Separating multilinear branching programs and formulas
Recommendations
Tensor-Rank and Lower Bounds for Arithmetic Formulas
We show that any explicit example for a tensor A : [n]r → F with tensor-rank ≥ nrċ(1−o(1)), where r = r(n) ≤ log n/log log n is super-constant, implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over F. This ...
Deterministic polynomial identity tests for multilinear bounded-read formulae
We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula, each variable occurs only a constant number of times, and each subformula computes a ...
Subexponential size hitting sets for bounded depth multilinear formulas
CCC '15: Proceedings of the 30th Conference on Computational ComplexityIn this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.
For depth-3 multilinear formulas, of size ...
Comments