Balancing syntactically multilinear arithmetic circuits

DOI10.1007/s00037-008-0254-0zbMath1188.68367OpenAlexW1988938797MaRDI QIDQ2269004

Amir Yehudayoff, Ran Raz

Publication date: 15 March 2010

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-008-0254-0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

Quadratic lower bounds for algebraic branching programs and formulas, Resource trade-offs in syntactically multilinear arithmetic circuits, Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications., Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication, Sums of read-once formulas: how many summands are necessary?, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, Arithmetic circuits: the chasm at depth four gets wider, Unnamed Item, Unnamed Item, A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas, Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications, Lower Bounds for Syntactically Multilinear Algebraic Branching Programs, Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae, Unnamed Item, Lower bounds for special cases of syntactic multilinear ABPs, Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree, Unnamed Item, Algebraic Complexity Classes, A quadratic lower bound for algebraic branching programs, A super-quadratic lower bound for depth four arithmetic circuits, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models, Unnamed Item, Short Proofs for the Determinant Identities, Limitations of sums of bounded read formulas and ABPs