TY - GEN

T1 - Tensor-rank and lower bounds for arithmetic formulas

AU - Raz, Ran

N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - We show that any explicit example for a tensor A:[n]r - → double-struck 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 double-struck 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.

AB - We show that any explicit example for a tensor A:[n]r - → double-struck 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 double-struck 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.

KW - arithmetic circuits

KW - homogenous circuits

KW - lower bounds

KW - multilinear circuits

KW - tensor rank

UR - http://www.scopus.com/inward/record.url?scp=77954692656&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954692656&partnerID=8YFLogxK

U2 - 10.1145/1806689.1806780

DO - 10.1145/1806689.1806780

M3 - Conference contribution

AN - SCOPUS:77954692656

SN - 9781605588179

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 659

EP - 666

BT - STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing

T2 - 42nd ACM Symposium on Theory of Computing, STOC 2010

Y2 - 5 June 2010 through 8 June 2010

ER -