Name
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 Galvinu0027s problem in extremal set theory. |
Year | Venue | DocType |
|---|---|---|
2017 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
24 | 0 | 0.34 |
References | Authors | |
18 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Ben Lee Volk | 2 | 12 | 5.62 |