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

DOI10.4086/TOC.2018.V014A016zbMATH Open1410.68125OpenAlexW2903016892MaRDI QIDQ4612480FDOQ4612480

Authors: Neeraj Kayal, Chandan Saha, Sébastien Tavenas 

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

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

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)

Cites Work

• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic circuits: the chasm at depth four gets wider
• Title not available (Why is that?)
• Lower bounds on arithmetic circuits via partial derivatives
• Arithmetic circuits: a chasm at depth 3
• An exponential lower bound for homogeneous depth four arithmetic formulas
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Factors of low individual degree polynomials
• Arithmetic circuits: a survey of recent results and open questions
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• A super-polynomial lower bound for regular arithmetic formulas
• 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
• On the Parallel Evaluation of Multivariate Polynomials
• Homogeneous formulas and symmetric polynomials
• Multi-\(k\)-ic depth three circuit lower bound
• On the power of homogeneous depth 4 arithmetic circuits
• On the size of homogeneous and of depth four formulas with low individual degree
• Improved bounds for reduction to depth 4 and depth 3
• Tensor-rank and lower bounds for arithmetic formulas
• Title not available (Why is that?)
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Depth-4 lower bounds, determinantal complexity: a unified approach
• The limits of depth reduction for arithmetic formulas: it's all about the top fan-in

Cited In (4)

• Multi-\(k\)-ic depth three circuit lower bound
• Title not available (Why is that?)
• An exponential lower bound for homogeneous depth four arithmetic formulas
• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree

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)