Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

RSS-Feed




Revision #1
Authors: Mrinal Kumar, Ben Lee Volk
Accepted on: 8th August 2017 13:43
Downloads: 40
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


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.



ISSN 1433-8092 | Imprint