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 (25)

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

This page was built for publication: Balancing syntactically multilinear arithmetic circuits