Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
Copyright policy )Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
We prove a lower bound of $Ω(n^2/\log^2 n)$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial $f(x_1, \ldots, x_n)$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([RSY08]), who proved a lower bound of $Ω(n^{4/3}/\log^2 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.
- Indian Institute of Technology Bombay India
- Leibniz Association Germany
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
- Tel Aviv University Israel
- Michigan State University United States
Circuit Lower Bounds, FOS: Computer and information sciences, lower bound on the size, Networks and circuits as models of computation; circuit complexity, Extremal set theory, syntactically multilinear arithmetic circuit, Computational Complexity (cs.CC), 004, Multilinear Circuits, Computer Science - Computational Complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Algebraic Complexity, ddc: ddc:004
Circuit Lower Bounds, FOS: Computer and information sciences, lower bound on the size, Networks and circuits as models of computation; circuit complexity, Extremal set theory, syntactically multilinear arithmetic circuit, Computational Complexity (cs.CC), 004, Multilinear Circuits, Computer Science - Computational Complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Algebraic Complexity, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!