Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR17-124 | 2nd November 2017 16:28

#### Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

Revision #2
Authors: Noga Alon, Mrinal Kumar, Ben Lee Volk
Accepted on: 2nd November 2017 16:28
Keywords:

Abstract:

We prove a lower bound of \$\Omega(n^2/\log^2 n)\$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial \$f(x_1, \ldots, x_n)\$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of \$\Omega(n^{4/3}/\log^2 n)\$ for the same polynomial. Our improvement follows from an asymptotically optimal lower bound for a generalized version of Galvin's problem in extremal set theory.

Changes to previous version:

The theorem on 'unbalancing set families' now works for a broad range of parameters. Earlier, it needed n = 4*prime, and set sizes to be at least log n.

Revision #1 to TR17-124 | 8th August 2017 13:42

#### An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

Revision #1
Authors: Mrinal Kumar, Ben Lee Volk
Accepted on: 8th August 2017 13:43
Keywords:

Abstract:

We prove a lower bound of \$\Omega(n^2/\log^2 n)\$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial \$f(x_1, \ldots, x_n)\$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of \$\Omega(n^{4/3}/\log^2 n)\$ for the same polynomial. Our improvement follows from an asymptotically optimal lower bound, in a certain range of parameters, for a generalized version of Galvin's problem in extremal set theory.

Changes to previous version:

Typos in the statement of Question 1.2.

### Paper:

TR17-124 | 6th August 2017 22:56

#### An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

TR17-124
Authors: Mrinal Kumar, Ben Lee Volk
Publication: 7th August 2017 09:23