Homogeneous formulas and symmetric polynomials

DOI10.1007/S00037-011-0007-3zbMATH Open1233.68230OpenAlexW2049156754MaRDI QIDQ649096FDOQ649096

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

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.

zbMATH Keywords

symmetric polynomialsalgebraic complexity

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Cites Work

• Title not available (Why is that?)
• Lower bounds on arithmetic circuits via partial derivatives
• Depth-3 arithmetic circuits over fields of characteristic zero
• On the depth complexity of formulas
• On the Parallel Evaluation of Multivariate Polynomials
• Title not available (Why is that?)
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Title not available (Why is that?)

Cited In (16)

• Title not available (Why is that?)
• On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
• Regular expression length via arithmetic formula complexity
• Monotone separations for constant degree polynomials
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• Title not available (Why is that?)
• 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
• A quadratic size-hierarchy theorem for small-depth multilinear formulas
• Schur polynomials do not have small formulas if the determinant does not
• On \(\epsilon\)-sensitive monotone computations
• 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)