A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

DOI10.1137/070707932zbMath1192.68329OpenAlexW2018202033MaRDI QIDQ3395047

Ran Raz, Amir Yehudayoff, Amir Shpilka

Publication date: 20 August 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070707932

zbMATH Keywords

explicit constructionslower boundsarithmetic circuits

Mathematics Subject Classification ID

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

Related Items (20)

Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Read-once polynomial identity testing ⋮ Recent Results on Polynomial Identity Testing ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Lower Bounds for Syntactically Multilinear Algebraic Branching Programs ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Towards Optimal Depth Reductions for Syntactically Multilinear Circuits ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits ⋮ Unifying known lower bounds via geometric complexity theory

This page was built for publication: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits