@inproceedings{7eca0b325f3c4aabaf8a9bab73cfb6fa,
title = "Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits",
abstract = "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.",
keywords = "Algebraic complexity, Circuit lower bounds, Multilinear circuits",
author = "Noga Alon and Mrinal Kumar and Volk, {Ben Lee}",
year = "2018",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.CCC.2018.11",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "111--1116",
editor = "Servedio, {Rocco A.}",
booktitle = "33rd Computational Complexity Conference, CCC 2018",
address = "Germany",
note = "33rd Computational Complexity Conference, CCC 2018 ; Conference date: 22-06-2018 Through 24-06-2018",
}