The shifted partial derivative complexity of elementary symmetric polynomials

DOI10.4086/TOC.2017.V013A009MaRDI QIDQ5368898zbMATH OpenOpenAlexFDO

Authors Nutan Limaye, Meena Mahajan, Srikanth Srinivasan, Hervé Fournier

Publication date 11 October 2017

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.2017.v013a009

zbMATH Keywords

arithmetic circuitsdepth-4 circuitsinclusion matrices

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• Affine projections of symmetric polynomials.
• Lower bounds on arithmetic circuits via partial derivatives
• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
• On the complexity of partial derivatives

Cited in

(8)

• On the linear independence of shifted powers
• Affine projections of symmetric polynomials.
• Partial derivatives in arithmetic complexity and beyond
• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• On the complexity of partial derivatives
• The method of shifted partial derivatives cannot separate the permanent from the determinant
• scientific article; zbMATH DE number 7561742 (Why is no real title available?)
• Schur polynomials do not have small formulas if the determinant does not

This page was built for publication: The shifted partial derivative complexity of elementary symmetric polynomials

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