Homogeneous formulas and symmetric polynomials
From MaRDI portal
Publication:649096
DOI10.1007/s00037-011-0007-3zbMath1233.68230OpenAlexW2049156754MaRDI QIDQ649096
Publication date: 30 November 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0007-3
Related Items (14)
Lower bounds for monotone counting circuits ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Monotone separations for constant degree polynomials ⋮ Unnamed Item ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ Regular expression length via arithmetic formula complexity ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on arithmetic circuits via partial derivatives
- On the depth complexity of formulas
- On the Parallel Evaluation of Multivariate Polynomials
- 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: Homogeneous formulas and symmetric polynomials
