TY - GEN
T1 - Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
AU - Alon, Noga
AU - Kumar, Mrinal
AU - Volk, Ben Lee
N1 - Funding Information:
Research supported in part by an ISF grant and by a GIF grant. 2 Part of this work was done while visiting Tel Aviv University. 3 The research leading to these results has received funding from the Israel Science Foundation (grant number 552/16).
Funding Information:
Research supported in part by an ISF grant and by a GIF grant. Part of this work was done while visiting Tel Aviv University. The research leading to these results has received funding from the Israel Science Foundation (grant number 552/16).
Publisher Copyright:
© Noga Alon, Mrinal Kumar, and Ben Lee Volk; licensed under Creative Commons License CC-BY 33rd Computational Complexity Conference (CCC 2018).
PY - 2018/6/1
Y1 - 2018/6/1
N2 - We prove a lower bound of Ω(n2/log n) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f(x1,⋯,xn). Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([31]), who proved a lower bound of Ω(n4/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.
AB - We prove a lower bound of Ω(n2/log n) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f(x1,⋯,xn). Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([31]), who proved a lower bound of Ω(n4/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.
KW - Algebraic complexity
KW - Circuit lower bounds
KW - Multilinear circuits
UR - http://www.scopus.com/inward/record.url?scp=85048952375&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048952375&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2018.11
DO - 10.4230/LIPIcs.CCC.2018.11
M3 - Conference contribution
AN - SCOPUS:85048952375
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 111
EP - 1116
BT - 33rd Computational Complexity Conference, CCC 2018
A2 - Servedio, Rocco A.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd Computational Complexity Conference, CCC 2018
Y2 - 22 June 2018 through 24 June 2018
ER -