Homogeneous formulas and symmetric polynomials

DOI10.1007/S00037-011-0007-3MaRDI QIDQ649096zbMATH OpenOpenAlexFDO

Authors Pavel Hrubeš, Amir Yehudayoff

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

zbMATH Keywords

symmetric polynomialsalgebraic complexity

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Recommendations

• Monotone separations for constant degree polynomials
• Tensor-rank and lower bounds for arithmetic formulas
• Tensor-rank and lower bounds for arithmetic formulas
• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
• Affine projections of symmetric polynomials.

Cites work

• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 3261634 (Why is no real title available?)
• scientific article; zbMATH DE number 3328173 (Why is no real title available?)
• Depth-3 arithmetic circuits over fields of characteristic zero
• Lower bounds on arithmetic circuits via partial derivatives
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• On the Parallel Evaluation of Multivariate Polynomials
• On the depth complexity of formulas

Cited in

(16)

• scientific article; zbMATH DE number 7561742 (Why is no real title available?)
• On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
• Monotone separations for constant degree polynomials
• Regular expression length via arithmetic formula complexity
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• scientific article; zbMATH DE number 5152087 (Why is no real title available?)
• Lower bounds for monotone counting circuits
• Non-commutative circuits and the sum-of-squares problem
• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
• EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS
• Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
• On \(\epsilon\)-sensitive monotone computations
• A quadratic size-hierarchy theorem for small-depth multilinear formulas
• Schur polynomials do not have small formulas if the determinant does not
• Tropical complexity, Sidon sets, and dynamic programming

This page was built for publication: Homogeneous formulas and symmetric polynomials

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