Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
Noga Alon, Mrinal Kumar, Ben Lee Volk · COMBINATORICA · 2020
We prove a lower bound of Ω ( n 2 /log 2 n ) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f ( x 1 ,..., x n ). Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([34]), who proved a lower bound of Ω ( 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. A special case of our combinatorial result implies, for every n , a tight Ω ( n ) lower bound on the minimum size of a family F of subsets of cardinality 2 n of a set X of size 4 n , so that any subset of X of size 2 n has intersection of size exactly n with some member of F . This settles a problem of Galvin up to a constant factor, extending results of Frankl and Rödl [15] and Enomoto et al. [12], who proved in 1987 the above statement (with a tight constant) for odd values of n , leaving the even case open.