The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials

DOI10.1007/978-3-662-48054-0_27MaRDI QIDQ2946403zbMATHOpenAlexFDO

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

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48054-0_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• The shifted partial derivative complexity of elementary symmetric polynomials
• On the complexity of symmetric polynomials
• scientific article; zbMATH DE number 165425
• On the complexity of the computation of certain classes of polynomials of several variables
• Partial derivatives in arithmetic complexity and beyond
• scientific article; zbMATH DE number 4070302
• Tropicalization, symmetric polynomials, and complexity
• scientific article; zbMATH DE number 18630
• Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
• On the complexity of partial derivatives

Cites work

• A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
• A super-polynomial lower bound for regular arithmetic formulas
• Affine projections of symmetric polynomials.
• An exponential lower bound for homogeneous depth four arithmetic formulas
• Approaching the chasm at depth four
• Arithmetic circuits: the chasm at depth four gets wider
• Communication Complexity
• Depth-3 arithmetic circuits over fields of characteristic zero
• Fast Parallel Computation of Polynomials Using Few Processors
• Homogeneous formulas and symmetric polynomials
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Lower bounds on arithmetic circuits via partial derivatives
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Separation of multilinear circuit and formula size
• Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
• The complexity of partial derivatives
• The limits of depth reduction for arithmetic formulas

Cited in

(7)

• Partial derivatives in arithmetic complexity and beyond
• Affine projections of symmetric polynomials.
• scientific article; zbMATH DE number 5849341 (Why is no real title available?)
• The method of shifted partial derivatives cannot separate the permanent from the determinant
• The shifted partial derivative complexity of elementary symmetric polynomials
• On the complexity of partial derivatives
• On the linear independence of shifted powers

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 Q2946403)