The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
DOI10.1007/978-3-662-48054-0_27zbMath1466.68041OpenAlexW1447393214MaRDI QIDQ2946403
Nutan Limaye, Srikanth Srinivasan, Meena Mahajan, 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
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
- Unnamed Item
- Arithmetic circuits: the chasm at depth four gets wider
- Homogeneous formulas and symmetric polynomials
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The complexity of partial derivatives
- Lower bounds on arithmetic circuits via partial derivatives
- A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
- Affine projections of symmetric polynomials.
- Improved Bounds for Reduction to Depth 4 and Depth 3
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- Fast Parallel Computation of Polynomials Using Few Processors
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- Communication Complexity
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- The limits of depth reduction for arithmetic formulas
- A super-polynomial lower bound for regular arithmetic formulas
- Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
- 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
This page was built for publication: The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
