Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2020 | Submitted
Journal Article Open

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


We prove a lower bound of Ω(n²/log²n) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f(x₁,...,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²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 2n of a set X of size 4n, so that any subset of X of size 2n 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.

Additional Information

© 2020 Springer Nature Switzerland AG. Part of Springer Nature. Received 10 June 2018; Revised 03 March 2019; Published 04 March 2020. Part of this work was done at the Center for Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, USA. Research supported in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation. Part of this work was done at the School of Computer Science, Tel Aviv University, Tel Aviv, Israel. The research leading to these results has received funding from the Israel Science Foundation (grant number 552/16).

Attached Files

Submitted - 1708.02037.pdf


Files (338.0 kB)
Name Size Download all
338.0 kB Preview Download

Additional details

August 19, 2023
August 19, 2023