### Abstract

We show that any explicit example for a tensor A:[n]^{r} - → double-struck F with tensor-rank ≥ n^{r·(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.

Original language | English (US) |
---|---|

Title of host publication | STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing |

Pages | 659-666 |

Number of pages | 8 |

DOIs | |

State | Published - Jul 23 2010 |

Externally published | Yes |

Event | 42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States Duration: Jun 5 2010 → Jun 8 2010 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | Cambridge, MA |

Period | 6/5/10 → 6/8/10 |

### All Science Journal Classification (ASJC) codes

- Software

### 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

*STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing*(pp. 659-666). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1806689.1806780