Multi-\(k\)-ic depth three circuit lower bound

DOI10.1007/s00224-016-9742-9zbMath1387.68113OpenAlexW3022488381MaRDI QIDQ1694000

Chandan Saha, Neeraj Kayal

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-016-9742-9

zbMATH Keywords

lower boundarithmetic circuitsevaluation dimensionmultilinear depth-three

Mathematics Subject Classification ID

Related Items (1)

On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arithmetic circuits: the chasm at depth four gets wider
• Lower bounds and separations for constant depth multilinear circuits
• Lower bounds on arithmetic circuits via partial derivatives
• Arithmetic Circuits: A Chasm at Depth 3
• Improved Bounds for Reduction to Depth 4 and Depth 3
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• Fast Parallel Computation of Polynomials Using Few Processors
• A super-polynomial lower bound for regular arithmetic formulas
• On the size of homogeneous and of depth four formulas with low individual degree
• Jacobian hits circuits
• Approaching the Chasm at Depth Four
• Multi-linear formulas for permanent and determinant are of super-polynomial size

This page was built for publication: Multi-\(k\)-ic depth three circuit lower bound