Computational complexity, Newton polytopes, and Schubert polynomials

Anshul Adve, Colleen Robichaux, Alexander Yong

Research output: Contribution to conferencePaperpeer-review

Abstract

The nonvanishing problem asks if a coefficient of a polynomial is nonzero. Many families of polynomials in algebraic combinatorics admit combinatorial counting rules and simultaneously enjoy having saturated Newton polytopes (SNP). Thereby, in amenable cases, nonvanishing is in the complexity class NP \ coNP of problems with "good characterizations". This suggests a new algebraic combinatorics viewpoint on complexity theory. This paper focuses on the case of Schubert polynomials. These form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. We give a tableau criterion for nonvanishing, from which we deduce the first polynomial time algorithm. These results are obtained from new characterizations of the Schubitope, a generalization of the permutahedron defined for any subset of the n n grid, together with a theorem of A. Fink, K. Mészáros, and A. St. Dizier (2018), which proved a conjecture of C. Monical, N. Tokcan, and the third author (2017).

Original languageEnglish (US)
StatePublished - 2019
Event31st International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2019 - Ljubljana, Slovenia
Duration: Jul 1 2019Jul 5 2019

Conference

Conference31st International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2019
CountrySlovenia
CityLjubljana
Period7/1/197/5/19

Keywords

  • Computational complexity
  • Newton polytopes
  • Schubert polynomials

ASJC Scopus subject areas

  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Computational complexity, Newton polytopes, and Schubert polynomials'. Together they form a unique fingerprint.

Cite this