Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

DOI10.4230/LIPICS.ICALP.2019.78MaRDI QIDQ5091237zbMATH OpenOpenAlexFDO

Authors

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1902.07063

zbMATH Keywords

lower boundsarithmetic circuitsdepth reductionmultilinear circuits

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Improved Bounds for Reduction to Depth 4 and Depth 3
• Improved bounds for reduction to depth 4 and depth 3
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• scientific article; zbMATH DE number 7250151
• Lower bounds and separations for constant depth multilinear circuits

Cites work

• scientific article; zbMATH DE number 7250151 (Why is no real title available?)
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Approaching the chasm at depth four
• Arithmetic circuits: a survey of recent results and open questions
• Arithmetic circuits: the chasm at depth four gets wider
• Improved bounds for reduction to depth 4 and depth 3
• Lower bounds and separations for constant depth multilinear circuits
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Non-commutative arithmetic circuits: depth reduction and size lower bounds

Cited in

(1)

• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree

This page was built for publication: Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

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