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

DOI10.4086/toc.2018.v014a016zbMath1410.68125OpenAlexW2903016892MaRDI QIDQ4612480

Sébastien Tavenas, Chandan Saha, Neeraj Kayal

Publication date: 31 January 2019

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

Full work available at URL: https://doi.org/10.4086/toc.2018.v014a016

zbMATH Keywords

lower boundsalgebraic complexitycomplexity theorypartial derivativesarithmetic circuitsarithmetic formulas

Mathematics Subject Classification ID

Related Items (2)

Unnamed Item ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Factors of low individual degree polynomials
• Arithmetic circuits: the chasm at depth four gets wider
• Lower bounds and separations for constant depth multilinear circuits
• Homogeneous formulas and symmetric polynomials
• Lower bounds on arithmetic circuits via partial derivatives
• Multi-\(k\)-ic depth three circuit lower bound
• Improved bounds for reduction to depth 4 and depth 3
• Arithmetic Circuits: A Chasm at Depth 3
• Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
• Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• On the Power of Homogeneous Depth 4 Arithmetic Circuits
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• On the Parallel Evaluation of Multivariate Polynomials
• A super-polynomial lower bound for regular arithmetic formulas
• On the size of homogeneous and of depth four formulas with low individual degree
• Tensor-Rank and Lower Bounds for Arithmetic Formulas
• Approaching the Chasm at Depth Four
• Multi-linear formulas for permanent and determinant are of super-polynomial size

This page was built for publication: On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree