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

(28)

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

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)