Sparse multivariate polynomial interpolation on the basis of Schubert polynomials

DOI10.1007/s00037-016-0142-yzbMath1383.68038arXiv1504.03856OpenAlexW3105806169MaRDI QIDQ1686837

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) Symmetric functions and generalizations (05E05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• SYMMETRICA
• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Schur times Schubert via the Fomin-Kirillov algebra
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Random arithmetic formulas can be reconstructed efficiently
• Read-once polynomial identity testing
• New results on noncommutative and commutative polynomial identity testing
• Sparse interpolation of symmetric polynomials
• Gröbner geometry of Schubert polynomials
• Interpolating polynomials from their values
• Schubert polynomials and the Littlewood-Richardson rule
• SYMMETRICA, an object oriented computer-algebra system for the symmetric group
• Completeness and reduction in algebraic complexity theory
• Yang-Baxter graphs, Jack and Macdonald polynomials
• Valiant's model and the cost of computing integers
• A structured view on weighted counting with relations to counting, quantum computation and applications
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• On P vs. NP and geometric complexity theory
• Arithmetic Circuits: A survey of recent results and open questions
• Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
• RC-Graphs and Schubert Polynomials
• Interpolating Arithmetic Read-Once Formulas in Parallel
• Skew Schubert polynomials
• Randomness efficient identity testing of multivariate polynomials
• Deciding Positivity of Littlewood--Richardson Coefficients
• Reconstruction of depth-4 multilinear circuits with top fan-in 2
• Affine projections of polynomials
• Efficient Reconstruction of Random Multilinear Formulas

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