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

DOI10.1007/s00493-019-4009-0zbMath1488.68027MaRDI QIDQ2204092

Noga Alon, Mrinal Kumar, Ben lee Volk

Publication date: 2 October 2020

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8879/

zbMATH Keywords

lower bound on the size; syntactically multilinear arithmetic circuit

Mathematics Subject Classification ID

05D05: Extremal set theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q06: Networks and circuits as models of computation; circuit complexity