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

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

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

**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.