A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
From MaRDI portal
Publication:3395047
DOI10.1137/070707932zbMath1192.68329MaRDI 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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications, Unnamed Item, Unnamed Item, A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas, 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, Non-commutative circuits and the sum-of-squares problem, Subexponential size hitting sets for bounded depth multilinear formulas, Resource trade-offs in syntactically multilinear arithmetic circuits, Read-once polynomial identity testing, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree, Unifying known lower bounds via geometric complexity theory, Algebraic Complexity Classes, A Selection of Lower Bounds for Arithmetic Circuits, 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
