Tensor-Rank and lower bounds for arithmetic formulas

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

We show that any explicit example for a tensor A : [ n]r\to F with tensor-rank /ge 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 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 homogeneous polynomial f of degree r, if there exists a (fanin-2) formula of size s and depth d for f then there exists a homogeneous formula of size O (( rd+r+1 ) · s )for f . In particular, for any r ≤ O(log n), if there exists a polynomial size formula for f then there exists a polynomial size homogeneous formula for f . This refutes a conjecture of Nisan and Wigderson [1996] and shows that superpolynomial lower bounds for homogeneous 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 ≤ O(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.

Original languageEnglish (US)
Article number40
JournalJournal of the ACM
Volume60
Issue number6
DOIs
StatePublished - Nov 1 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Arithmetic circuits
  • Homogenous circuits
  • Lower bounds
  • Multilinear circuits
  • Tensor rank

Fingerprint Dive into the research topics of 'Tensor-Rank and lower bounds for arithmetic formulas'. Together they form a unique fingerprint.

  • Cite this