Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits

Noga Alon, Mrinal Kumar, Ben Lee Volk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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.

Original languageEnglish (US)
Title of host publication33rd Computational Complexity Conference, CCC 2018
EditorsRocco A. Servedio
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages111-1116
Number of pages1006
ISBN (Electronic)9783959770699
DOIs
StatePublished - Jun 1 2018
Externally publishedYes
Event33rd Computational Complexity Conference, CCC 2018 - San Diego, United States
Duration: Jun 22 2018Jun 24 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume102
ISSN (Print)1868-8969

Other

Other33rd Computational Complexity Conference, CCC 2018
CountryUnited States
CitySan Diego
Period6/22/186/24/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Algebraic complexity
  • Circuit lower bounds
  • Multilinear circuits

Fingerprint Dive into the research topics of 'Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Kumar, M., & Volk, B. L. (2018). Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. In R. A. Servedio (Ed.), 33rd Computational Complexity Conference, CCC 2018 (pp. 111-1116). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 102). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2018.11