Balancing syntactically multilinear arithmetic circuits

DOI10.1007/S00037-008-0254-0MaRDI QIDQ2269004zbMATH OpenOpenAlexFDO

Authors Ran Raz, Amir Yehudayoff

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)

Recommendations

• scientific article; zbMATH DE number 7250151
• Separation of multilinear circuit and formula size
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• Lower bounds and separations for constant depth multilinear circuits

Cited in

(31)

• Sums of read-once formulas: how many summands are necessary?
• Limitations of sums of bounded read formulas and ABPs
• Quadratic lower bounds for algebraic branching programs and formulas
• 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
• Some lower bound results for set-multilinear arithmetic computations
• Algebraic complexity classes
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Separation of multilinear circuit and formula size
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• Resource trade-offs in syntactically multilinear arithmetic circuits
• Arithmetic circuits: the chasm at depth four gets wider
• scientific article; zbMATH DE number 7009617 (Why is no real title available?)
• Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
• On proving parameterized size lower bounds for multilinear algebraic models
• A quadratic size-hierarchy theorem for small-depth multilinear formulas
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• Lower bounds for multilinear order-restricted ABPs
• A quadratic lower bound for algebraic branching programs
• A super-quadratic lower bound for depth four arithmetic circuits
• scientific article; zbMATH DE number 7250151 (Why is no real title available?)
• Short Proofs for the Determinant Identities
• Lower bounds for special cases of syntactic multilinear ABPs
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Lower bounds for the sum of small-size algebraic branching programs
• Lower bounds for set-multilinear branching programs
• Lower bounds for the sum of small-size algebraic branching programs
• Lower bounds for set-multilinear branching programs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2269004)