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

DOI10.4086/TOC.2018.V014A016MaRDI QIDQ4612480zbMATH OpenOpenAlexFDO

Authors Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Publication date 31 January 2019

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

partial derivativeslower boundscomplexity theoryarithmetic circuitsalgebraic complexityarithmetic formulas

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the size of homogeneous and of depth four formulas with low individual degree
• An exponential lower bound for homogeneous depth four arithmetic formulas
• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
• On varieties of almost minimal degree II: A rank-depth formula
• Decomposition of graphs and monotone formula size of homogeneous functions
• Homogeneous forms of odd degree in a large number of variables
• scientific article; zbMATH DE number 4085724
• A quadratic size-hierarchy theorem for small-depth multilinear formulas

Cites work

• scientific article; zbMATH DE number 1775446 (Why is no real title available?)
• scientific article; zbMATH DE number 7204282 (Why is no real title available?)
• A super-polynomial lower bound for regular arithmetic formulas
• An exponential lower bound for homogeneous depth four arithmetic formulas
• Approaching the chasm at depth four
• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: a survey of recent results and open questions
• Arithmetic circuits: the chasm at depth four gets wider
• Depth-4 lower bounds, determinantal complexity: a unified approach
• Factors of low individual degree polynomials
• Fast Parallel Computation of Polynomials Using Few Processors
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• Homogeneous formulas and symmetric polynomials
• Improved bounds for reduction to depth 4 and depth 3
• Lower bounds and separations for constant depth multilinear circuits
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Lower bounds on arithmetic circuits via partial derivatives
• Multi-\(k\)-ic depth three circuit lower bound
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• On the Parallel Evaluation of Multivariate Polynomials
• On the power of homogeneous depth 4 arithmetic circuits
• On the size of homogeneous and of depth four formulas with low individual degree
• Tensor-rank and lower bounds for arithmetic formulas
• The limits of depth reduction for arithmetic formulas: it's all about the top fan-in

Cited in

(7)

• Multi-\(k\)-ic depth three circuit lower bound
• Multi-\(k\)-ic depth three circuit lower bound
• Lower bounds for the circuit size of partially homogeneous polynomials
• On the size of homogeneous and of depth four formulas with low individual degree
• scientific article; zbMATH DE number 7559443 (Why is no real title available?)
• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
• An exponential lower bound for homogeneous depth four arithmetic formulas

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

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