The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
DOI10.1007/978-3-662-48054-0_27zbMATH Open1466.68041OpenAlexW1447393214MaRDI QIDQ2946403FDOQ2946403
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
Recommendations
- The shifted partial derivative complexity of elementary symmetric polynomials
- scientific article; zbMATH DE number 7559090
- 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
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)
Cites Work
- The complexity of partial derivatives
- Communication Complexity
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic circuits: the chasm at depth four gets wider
- A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Lower bounds on arithmetic circuits via partial derivatives
- Improved Bounds for Reduction to Depth 4 and Depth 3
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- Separation of multilinear circuit and formula size
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- 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
- Depth-3 arithmetic circuits over fields of characteristic zero
- Homogeneous formulas and symmetric polynomials
- Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
- The limits of depth reduction for arithmetic formulas
- Affine projections of symmetric polynomials.
Cited In (3)
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)
