Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

DOI10.4230/LIPICS.ICALP.2019.78OpenAlexW2963003754MaRDI QIDQ5091237FDOQ5091237

Authors:

Publication date: 21 July 2022

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

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

zbMATH Keywords

lower boundsarithmetic circuitsdepth reductionmultilinear circuits

Mathematics Subject Classification ID

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

Cites Work

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

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)