Sparse multivariate polynomial interpolation on the basis of Schubert polynomials

DOI10.1007/S00037-016-0142-YMaRDI QIDQ1686837zbMATH OpenOpenAlexFDO

Authors Priyanka Mukhopadhyay, Youming Qiao

Publication date 18 December 2017

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.03856

zbMATH Keywords

Schubert polynomials\#Psparse interpolationVNP

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symmetric functions and generalizations (05E05)

Abstract: Schubert polynomials were discovered by A. Lascoux and M. Sch"utzenberger in the study of cohomology rings of flag manifolds in 1980's. These polynomials generalize Schur polynomials, and form a linear basis of multivariate polynomials. In 2003, Lenart and Sottile introduced skew Schubert polynomials, which generalize skew Schur polynomials, and expand in the Schubert basis with the generalized Littlewood-Richardson coefficients. In this paper we initiate the study of these two families of polynomials from the perspective of computational complexity theory. We first observe that skew Schubert polynomials, and therefore Schubert polynomials, are in $CountP$ (when evaluating on non-negative integral inputs) and $VNP$. Our main result is a deterministic algorithm that computes the expansion of a polynomial $f$ of degree $d$ in $$ in the basis of Schubert polynomials, assuming an oracle computing Schubert polynomials. This algorithm runs in time polynomial in $n$, $d$, and the bit size of the expansion. This generalizes, and derandomizes, the sparse interpolation algorithm of symmetric polynomials in the Schur basis by Barvinok and Fomin (Advances in Applied Mathematics, 18(3):271--285). In fact, our interpolation algorithm is general enough to accommodate any linear basis satisfying certain natural properties. Applications of the above results include a new algorithm that computes the generalized Littlewood-Richardson coefficients.

Recommendations

• Using Schubert basis to compute with multivariate polynomials
• On formulas and some combinatorial properties of Schubert polynomials
• An efficient algorithm for deciding vanishing of Schubert polynomial coefficients
• Sparse interpolation of symmetric polynomials
• Multiplication of a Schubert polynomial by a Schur polynomial

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3779503 (Why is no real title available?)
• scientific article; zbMATH DE number 2038300 (Why is no real title available?)
• A structured view on weighted counting with relations to counting, quantum computation and applications
• Affine projections of polynomials (extended abstract)
• Arithmetic circuits: a survey of recent results and open questions
• Completeness and reduction in algebraic complexity theory
• Deciding positivity of Littlewood-Richardson coefficients
• Efficient Reconstruction of Random Multilinear Formulas
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Gröbner geometry of Schubert polynomials
• Interpolating Arithmetic Read-Once Formulas in Parallel
• Interpolating polynomials from their values
• Interpolation of depth-3 arithmetic circuits with two multiplication gates
• New results on noncommutative and commutative polynomial identity testing
• On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• RC-Graphs and Schubert Polynomials
• RC-graphs and a generalized Littlewood-Richardson rule
• Random arithmetic formulas can be reconstructed efficiently
• Randomness efficient identity testing of multivariate polynomials
• Read-once polynomial identity testing
• Reconstruction of depth-4 multilinear circuits with top fan-in 2
• SYMMETRICA, an object oriented computer-algebra system for the symmetric group
• Schubert polynomials and the Littlewood-Richardson rule
• Schur times Schubert via the Fomin-Kirillov algebra
• Skew Schubert polynomials
• Sparse interpolation of symmetric polynomials
• Symmetric functions, Schubert polynomials and degeneracy loci. Transl. from the French by John R. Swallow
• Valiant's model and the cost of computing integers
• Yang-Baxter graphs, Jack and Macdonald polynomials

Cited in

(7)

• Robust algorithms for sparse interpolation of multivariate polynomials
• Tropicalization, symmetric polynomials, and complexity
• An efficient algorithm for deciding vanishing of Schubert polynomial coefficients
• An SVD analysis of equispaced polynomial interpolation
• Multivariate polynomials in Sage
• Sparse polynomial interpolation in Chebyshev bases
• Using Schubert basis to compute with multivariate polynomials

Describes a project that uses

Uses Software

• SYMMETRICA
• lowerbounds-survey
• GitHub

This page was built for publication: Sparse multivariate polynomial interpolation on the basis of Schubert polynomials

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