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

Noga Alon; Mrinal Kumar; Ben Lee Volk

doi:10.4230/LIPIcs.CCC.2018.11

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 proceeding › Conference contribution

6 Scopus citations

Abstract

We prove a lower bound of Ω(n²/log n) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f(x1,⋯,x_n). Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([31]), who proved a lower bound of Ω(n⁴/³/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 language	English (US)
Title of host publication	33rd Computational Complexity Conference, CCC 2018
Editors	Rocco A. Servedio
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	111-1116
Number of pages	1006
ISBN (Electronic)	9783959770699
DOIs	https://doi.org/10.4230/LIPIcs.CCC.2018.11
State	Published - Jun 1 2018
Externally published	Yes
Event	33rd Computational Complexity Conference, CCC 2018 - San Diego, United States Duration: Jun 22 2018 → Jun 24 2018

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	102
ISSN (Print)	1868-8969

Other

Other	33rd Computational Complexity Conference, CCC 2018
Country	United States
City	San Diego
Period	6/22/18 → 6/24/18

All Science Journal Classification (ASJC) codes

Software

Keywords

Algebraic complexity
Circuit lower bounds
Multilinear circuits

Access to Document

10.4230/LIPIcs.CCC.2018.11

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

Alon, Noga ; Kumar, Mrinal ; Volk, Ben Lee. / Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. 33rd Computational Complexity Conference, CCC 2018. editor / Rocco A. Servedio. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. pp. 111-1116 (Leibniz International Proceedings in Informatics, LIPIcs).

@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",

}

Alon, N, Kumar, M & Volk, BL 2018, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. in RA Servedio (ed.), 33rd Computational Complexity Conference, CCC 2018. Leibniz International Proceedings in Informatics, LIPIcs, vol. 102, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 111-1116, 33rd Computational Complexity Conference, CCC 2018, San Diego, United States, 6/22/18. https://doi.org/10.4230/LIPIcs.CCC.2018.11

Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. / Alon, Noga; Kumar, Mrinal; Volk, Ben Lee.

33rd Computational Complexity Conference, CCC 2018. ed. / Rocco A. Servedio. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. p. 111-1116 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 102).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

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 -

Alon N, Kumar M, Volk BL. Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. In Servedio RA, editor, 33rd Computational Complexity Conference, CCC 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. p. 111-1116. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.CCC.2018.11