On the complexity of symmetric polynomials

DOI10.4230/LIPICS.ITCS.2019.47MaRDI QIDQ5090425zbMATH OpenFDO

Authors Markus Bläser, Gorav Jindal

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2019.47

zbMATH Keywords

arithmetic circuitsarithmetic complexityelementary symmetric polynomialsNewton's iterationpower seriessymmetric polynomials

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Affine projections of symmetric polynomials.
• Homogeneous formulas and symmetric polynomials
• How symmetric can a function be?
• On the Symmetries of and Equivalence Test for Design Polynomials.
• EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS

Cites work

• Algebraic complexity classes
• All Algebraic Functions Can Be Computed Fast
• Completeness and reduction in algebraic complexity theory
• Computational Complexity
• Evaluation properties of invariant polynomials
• EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS
• scientific article; zbMATH DE number 3568615 (Why is no real title available?)
• On the Complexity of Numerical Analysis
• Short presentations for alternating and symmetric groups
• Solving multivariate algebraic equation by Hensel construction
• The Fundamental Theorem on Symmetric Polynomials: History's First Whiff of Galois Theory

Cited in

(16)

• On polynomials with symmetric Galois group which are easy to compute
• Rewriting techniques and degree bounds for higher order symmetric polynomials.
• Computing critical points for invariant algebraic systems
• Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols
• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• scientific article; zbMATH DE number 5849341 (Why is no real title available?)
• scientific article; zbMATH DE number 3968581 (Why is no real title available?)
• Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
• On the Symmetries of and Equivalence Test for Design Polynomials.
• Concrete Multiplicative Complexity of Symmetric Functions
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Schur polynomials do not have small formulas if the determinant does not
• Symmetric arithmetic circuits
• Computing polynomial representation in subrings of multivariate polynomial rings
• Deciding connectivity in symmetric semi-algebraic sets
• Tight bounds for the multiplicative complexity of symmetric functions

This page was built for publication: On the complexity of symmetric polynomials

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