Ran Raz
ABSTRACT
We show that any explicit example for a tensor A:[n]r -> F with tensor-rank ≥ nr ⋅ (1- o(1)), (where r ≤ log n / log log n), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over F. This shows that strong enough lower bounds for the size of arithmetic formulas of depth 3 imply super-polynomial lower bounds for the size of general arithmetic formulas. One component of our proof is a new approach for homogenization and multilinearization of arithmetic formulas, that gives the following results: We show that for any n-variate homogenous polynomial f of degree r, if there exists a (fanin-2) formula of size s and depth d for f then there exists a homogenous formula of size O ( d+r+1/r ⋅ s) for f. In particular, for any r ≤ log n / log log n, r ≤ log n, if there exists a polynomial size formula for f then there exists a polynomial size homogenous formula for f. This refutes a conjecture of Nisan and Wigderson [10] and shows that super-polynomial lower bounds for homogenous formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas. We show that for any n-variate set-multilinear polynomial f of degree r, if there exists a (fanin-2) formula of size s and depth d for f then there exists a set-multilinear formula of size O ( (d+2)r ⋅ s ) for f. In particular, for any r ≤ log n / log log n, if there exists a polynomial size formula for f then there exists a polynomial size set-multilinear formula for f. This shows that super-polynomial lower bounds for set-multilinear formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.
- S. Aaronson. Multilinear Formulas and Skepticism of Quantum Computing. STOC 2004: 118--127 Google Scholar
Digital Library
- M. Agrawal, V. Vinay. Arithmetic Circuits: A Chasm at Depth Four. FOCS 2008: 67--75 Google ScholarDigital Library
- W. Baur, V. Strassen. The Complexity of Partial Derivatives. Theor. Comput. Sci. 22: 317--330 (1983)Google ScholarCross Ref
- J. von zur Gathen. Algebraic Complexity Theory. Ann. Rev. Computer Science 3: 317--347 (1988) Google ScholarDigital Library
- D. Grigoriev, M. Karpinski. An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC 1998: 577--582 Google ScholarDigital Library
- D. Grigoriev, A. A. Razborov. Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. Applicable Algebra in Engineering, Communication and Computing 10(6): 465--487 (2000) (preliminary version in FOCS 1998)Google Scholar
- J. Håstad. Tensor Rank is NP-Complete. J. Algorithms 11(4): 644--654 (1990)(preliminary version in ICALP 1989) Google ScholarDigital Library
- P. Hrubes, A. Yehudayoff. Homogeneous Formulas and Symmetric Polynomials, Manuscript 2009Google Scholar
- N. Nisan. Lower Bounds for Non--Commutative Computation. STOC 1991: 410--418 Google ScholarDigital Library
- N. Nisan, A. Wigderson. Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity 6(3): 217--234 (1996) (preliminary version in FOCS 1995) Google ScholarDigital Library
- R. Raz. Multi--Linear Formulas for Permanent and Determinant are of Super-Polynomial Size. J. ACM 56(2) (2009) (Preliminary version in STOC 2004) Google ScholarDigital Library
- R. Raz. Separation of Multilinear Circuit and Formula Size. Theory Of Computing 2(6) (2006) (preliminary version in FOCS 2004, title: Multilinear-NC_1 ≠ Multilinear-NC_2) Google ScholarDigital Library
- R. Raz. Elusive Functions and Lower Bounds for Arithmetic Circuits. STOC 2008: 711--720 Google ScholarDigital Library
- R. Raz, A. Shpilka, A. Yehudayoff. A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. SIAM J. Comput. 38(4): 1624--1647 (2008)(preliminary version in FOCS 2007) Google ScholarDigital Library
- R. Raz, A. Yehudayoff. Multilinear Formulas,Maximal-Partition Discrepancy and Mixed-Sources Extractors. FOCS 2008: 273--282 Google ScholarDigital Library
- R. Raz, A. Yehudayoff. Lower Bounds and Separations for Constant Depth Multilinear Circuits. IEEE Conference on Computational Complexity 2008: 128--139 Google ScholarDigital Library
- V. Strassen. Vermeidung von Divisionen. J. Reine Angew. Math. 264: 182--202 (1973)Google Scholar
- L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput. 12(4): 641--644 (1983)Google ScholarCross Ref
Index Terms
- Tensor-rank and lower bounds for arithmetic 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 ...
Lower bounds for depth 4 formulas computing iterated matrix multiplication
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computingWe study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMMn,d, has size nΩ(√d) as long as d = nO(1). This ...
Elusive functions and lower bounds for arithmetic circuits
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingA basic fact in linear algebra is that the image of the curve f(x)=(x1,x2,x3,...,xm), say over C, is not contained in any m-1 dimensional affine subspace of Cm. In other words, the image of f is not contained in the image of any polynomial-mapping Γ:Cm-...
Comments