Pith. sign in

REVIEW 1 major objections 4 minor 113 references

Vanishing of Schubert Coefficients

T0 review · 1 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The vanishing of Schubert coefficients is in coAM under GRH, placing it in the second level of the polynomial hierarchy, for the first time.

desk verdict First PH upper bound for Schubert vanishing via a clean reduction to parametric Nullstellensatz; the type D appendix is the soft spot and Table 2 needs fixing. read the letter →

arxiv 2412.02064 v3 pith:WBDOMYCZ submitted 2024-12-03 math.CO cs.CCcs.DMmath.AG

Igor Pak , Colleen Robichaux This is my paper · ORCID
classification math.COcs.CCcs.DMmath.AG MSC 14M1505E9968Q25
keywords SchubertcoefficientsvanishingproblemcomplexityclassespolynomialhierarchycoAMHilbertNullstellensatzliftedformulationsclassicalLietypes
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that the problem of deciding whether a Schubert coefficient $c^w_{u,v}$ is zero belongs to the complexity class coAM, assuming the Generalized Riemann Hypothesis. Since coAM is contained in the second level of the polynomial hierarchy $\Sigma_2^p$, this gives the first upper bound placing the Schubert vanishing problem inside ${\sf PH}$. The result holds for the classical types A, B, C, and D. Previously only the ${\sf PSPACE}$ upper bound was known, and the paper explains why a natural ${\sf C_{=}P}$ upper bound does not by itself imply a ${\sf PH}$ upper bound.

What carries the argument

The central mechanism is the lifted formulation: a polynomial system with $O(n^2)$ equations and variables, with coefficients depending polynomially on parameters $y,z$, such that for generic parameter values the number of solutions over $\mathbb{C}$ equals the Schubert coefficient. For nonvanishing, the system has a solution over the function field $\mathbb{C}(y,z)$ exactly when the coefficient is positive. In type D the new machinery is the double-coset intersection criterion: $c^w_{u,v}(Y)>0$ iff $B^- \dot{u} B \cap \pi B^- \dot{v} B \cap \rho B^- \dot{w_0 w} B$ is nonempty for generic $\pi,\rho$, together with polynomial-size descriptions of generic group elements via Cayley transforms and of Borel subgroups via triangular matrix equations.

What would settle it

Find a concrete triple of permutations $u,v,w$ in type D for which the system $E^D(u,v,w)$ of Appendix C has a solution over $\mathbb{C}(y,z)$ but the Schubert coefficient $c^w_{u,v}(D)$ is zero, or vice versa. Because the system size is $O(n^2)$, this can be checked by explicit computation for small $n$, for instance $n=4$ or $n=5$, using exact arithmetic over function fields, and any mismatch would refute the main reduction for type D.

Watch

Extended reading notes

Core claim

The paper's central claim is that the vanishing problem $\{c^w_{u,v}=^? 0\}$ is in ${\sf coAM}$ under GRH. The proof works by reducing the nonvanishing problem to an instance of the Parametric Hilbert Nullstellensatz (HNP), a decision problem that was recently shown to be in ${\sf AM}$ under GRH. The reduction uses 'lifted formulations': polynomial systems whose number of solutions over the function field $\mathbb{C}(y,z)$ counts the Schubert coefficient, and whose existence of a solution characterizes nonvanishing. For types A, B, and C the lifted formulations come from Stiefel coordinates and bilinear incidence equations; for type D the paper supplies a new construction (jointly with David Speyer) based on double-coset intersections and Borel subgroup equations, which avoids the exponentially large determinant equation that blocked the earlier approach.

Load-bearing premise

The entire argument rests on the availability of polynomial-size lifted polynomial systems whose satisfiability exactly matches nonvanishing of the Schubert coefficient, and for type D this depends on the Appendix C claim (Equation C.1) that the double-coset intersection is nonempty for generic $\pi,\rho$ exactly when $c^w_{u,v}>0$, together with the Borel parametrization tables correctly encoding membership in the Borel subgroups of $SO_{2n}$.

Editorial extensions

If this is right

  • Assuming GRH, SchubertVanishing is in coAM, hence inside $\Sigma_2^p$: the first polynomial-hierarchy upper bound for this problem. As a consequence, the vanishing problem cannot be NP-complete unless PH collapses to the second level.
  • Since positive Schubert coefficients would be witnessed by an HNP solution when GRH holds, the paper identifies a structural obstacle to proving Conjecture 1.3 (Schubert not in $\#{\sf P}$) by showing the vanishing problem is not in PH.
  • The result extends to the vanishing problem for generic $k$-fold intersections of Schubert varieties for every fixed $k$, as noted in the final remarks.
  • In the BSS model over the complex numbers, the same lifted formulations place nonvanishing in ${\sf NP}_{\mathbb{C}}$ and Schubert coefficient computation in $\#{\sf P}_{\mathbb{C}}$ in all classical types.
  • The type D construction (Appendix C) also gives a new uniform proof of the reduction for types A, B and C, replacing the earlier Stiefel-coordinate systems with double-coset equations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the HNP-in-AM theorem were ever derandomized, the GRH assumption could likely be removed and the vanishing problem would probably land in NP or coNP, which would contradict the paper's Conjecture 1.5 but would strengthen the case that combinatorial witnesses exist.
  • The double-coset construction in Appendix C suggests that other cohomological structure constants definable by generic intersections of Schubert varieties—not only the classical types—might admit polynomial-size lifted formulations, as long as the group and flag conditions can be encoded with polynomial-size equations.
  • A natural testable extension is to apply the same lifted-formulation method to the vanishing of equivariant Schubert coefficients or to quiver coefficients, where the geometric counting interpretation is similar but the defining systems are not yet known to be polynomial-size.
  • The paper's framework indicates that the difficulty in type D was not geometric but computational: the determinant $\det(\omega)=1$ condition is of exponential size, so any improvement must avoid explicitly encoding that equation; the new construction does so by working directly with double cosets and Borel subgroups.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies the decision problem SchubertVanishing: given permutations u,v,w in the Weyl group of one of the classical types A,B,C,D, is the Schubert structure constant c^w_{u,v} equal to 0? The main theorem (Theorem 1.4) states that, assuming GRH, SchubertVanishing is in coAM, and hence in Sigma_2^p, for types A,B,C,D. The proof reduces the negation of SchubertVanishing to the Parametric Hilbert Nullstellensatz (HNP), which was recently shown to be in AM by Ait El Manssour et al. For types A,B,C the reduction is via explicit lifted formulations whose number of solutions over C(y,z) equals the corresponding Schubert coefficient (Propositions 5.2, 6.2, 6.3). For type D the paper relies on a new appendix (joint with Speyer) that constructs a uniform HN system for all classical types from the double-coset description of Schubert intersections. The paper also contains BSS-model results and a discussion of conjectures around #P-hardness of Schubert coefficients.

Significance. The main result, if correct, would be the first nontrivial upper bound in the polynomial hierarchy for the Schubert vanishing problem, a problem for which only PSPACE and C=P bounds were previously known. The construction is explicit and polynomial-sized, and it builds on the recent HNP result without circularity: the reduction uses Kleiman transversality, the Billey-Haiman relation, and external theorems, and does not assume the vanishing problem. The paper also makes the case that the vanishing problem is unlikely to be coNP-hard under standard derandomization assumptions. The main caveat is that the type D case depends on the Appendix C encoding of Borel subgroups; as printed, that encoding is incomplete, so the central claim as stated is not yet fully supported.

major comments (1)
  1. [Appendix C, Table 2 and C.4] In the rows for SO_{2n+1}, Sp_{2n}, and SO_{2n}, the set Eq(B) is printed as only the diagonal conditions b_{ii} b_{(2n+2-i)(2n+2-i)}=1 (plus a determinant condition in the odd orthogonal case). These conditions are necessary but not sufficient for B to lie in G: for example, for SO_4 with J=D_4, the upper-triangular matrix B=I+E_{12} satisfies all printed diagonal equations but violates B^T J B=J. Since the system E_Y(u,v,w) in C.4 is explicitly assembled from Eq(P_i) and Eq(Q_i) 'in Table 2', the satisfiability of E_Y as written is not equivalent to the non-emptiness of the double-coset intersection Xi in Equation (C.2). Therefore the 'if and only if' in the proof of Lemma C.1 is not established for types B, C, and D. The prose in C.3 says that B^T J B=J is imposed, but this matrix equation never appears in Table 2 or in C.4. The authors should either include the full matrix equation in E_Y (this adds O(n^2) equations, preserving the HNP reduction) or prove that the enlarged system has the same satisfiability over C(y,z). As printed, this is a load-bearing gap in the proof of Theorem 1.4 for type D.
minor comments (4)
  1. [Appendix C, Table 2, SO_{2n+1} row] The determinant condition is printed as 'bnn=1'; in the stated conventions this should be b_{n+1,n+1}=1, and the surrounding text 'det(B)=bnn' in C.3 has the same indexing issue. This typo, together with the missing matrix equations, suggests the table needs a careful rewrite.
  2. [Appendix A and Table 1, SO_{2n}] The parameter set for M is listed as {m_{ij}}_{i+j <= 2n+1} and the text says t=2n^2+n, but equation (A.2) forces the antidiagonal entries m_{i,2n+1-i} to vanish, so the dimension of so(2n) is n(2n-1)=2n^2-n. Please correct the parameter count or the index bound.
  3. [Abstract] The phrase 'whether c^w_{u,v} in #P' should be phrased as whether the function (u,v,w) |-> c^w_{u,v} is in #P, since a coefficient is an integer rather than a counting function.
  4. [Section 2.2(2)] The statement that Theorem 1.4 implies 'there are currently no other tools' to attack Conjecture 1.3 is too strong; the theorem rules out a particular route, not the existence of all possible tools.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the coAM upper bound follows from an external HNP-in-AM theorem and explicit polynomial systems for nonvanishing.

full rationale

The claimed derivation chain is not circular. Schubert coefficients are expressed as generic intersections via Kleiman transversality (Eq. 4.3), and the paper then constructs polynomial systems whose number of solutions equals the corresponding Schubert coefficient (Propositions 5.2, 6.2, 6.3; Lemma C.1). Satisfiability of these systems is therefore equivalent to nonvanishing, and the final complexity bound is obtained by reducing to the parametric Hilbert Nullstellensatz result of Ait El Manssour et al. [A+24], whose authors do not overlap with the present paper. No fitted parameter is relabeled as a prediction, and no step reduces Schubert vanishing to a theorem of the present authors: the Billey–Haiman relation used for type B is an external result, and the self-citations to [PR24a], [PR24b], and [PR24c] are contextual rather than load-bearing. The printed Table 2 Borel equations in Appendix C may raise a correctness concern about whether they fully encode membership in the Borel subgroup for SO/Sp types, but that is an error-risk issue, not circularity; it does not make the conclusion equivalent to an input by construction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central theorem is conditional on GRH and on the recent HNP result of Ait El Manssour et al. The paper contributes polynomial-time reductions from nonvanishing of Schubert coefficients to HNP, with explicit polynomial systems of O(n^2) size. No free parameters are fitted to data; all remaining axioms are standard theorems in Schubert calculus and complexity theory or the explicitly stated GRH assumption.

assumptions (6)
  • domain assumption Generalized Riemann Hypothesis (GRH): nontrivial zeros of Dirichlet L-functions lie on the critical line.
    Invoked through Koiran's theorem and the HNP theorem of Ait El Manssour et al. to obtain AM membership of HN/HNP; Main Theorem 1.4 is explicitly conditional on GRH.
  • domain assumption Parametric Hilbert Nullstellensatz HNP is in AM assuming GRH (Ait El Manssour et al., Theorem 1).
    Load-bearing external theorem. Without it, Lemma 1.9 only gives membership in HNP, not in AM or PH.
  • standard math Kleiman transversality: generically translated Schubert varieties intersect transversely and c^w_{u,v} counts points in the triple intersection.
    Used in Equation (4.3), in the proof of Proposition 5.2, and in Equation (C.1).
  • standard math Lifted formulation characterization of Schubert cells from Hein-Sottile (Proposition 5.1) and its analogues in types C and D.
    The polynomial systems S^Y are built from this characterization; if it failed, solution counts would not match Schubert coefficients.
  • standard math Billey-Haiman relation c^w_{u,v}(B)=2^{s(w)-s(u)-s(v)} c^w_{u,v}(C).
    Used in Proposition 6.3 to transfer the type C system to type B.
  • standard math Purbhoo's linear algebra criterion for nonvanishing of Schubert coefficients (Lemma B.7).
    Used for the BSS-model upper bound in Theorem B.3; not needed for Main Theorem 1.4 but supports additional claims in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Vanishing of Schubert Coefficients." pith.science (2026). https://pith.science/paper/WBDOMYCZ

@misc{pith2026241202064,
  author       = {Pith},
  title        = {Pith review of: Vanishing of Schubert Coefficients},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WBDOMYCZ}},
  note         = {Machine review of arXiv:2412.02064}
}
abstract

Schubert coefficients are nonnegative integers $c^w_{u,v}$ that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. It is a major open problem whether they have a combinatorial interpretation, i.e, whether $c^w_{u,v} \in \#{\sf P}$. We study the closely related vanishing problem of Schubert coefficients: $\{c^w_{u,v}=^? 0\}$. Until this work it was open whether this problem is in the polynomial hierarchy ${\sf PH}$. We prove that $\{c^w_{u,v}=^? 0\}$ in ${\sf coAM}$ assuming the GRH. In particular, the vanishing problem is in ${\Sigma_2^{{\text{p}}}}$. Our approach is based on constructions lifted formulations, which give polynomial systems of equations for the problem. The result follows from a reduction to Parametric Hilbert's Nullstellensatz, recently studied in arXiv:2408.13027. We extend our results to all classical types. Type $D$ is resolved in the appendix (joint with David Speyer).

Figures

Figures reproduced from arXiv: 2412.02064 by the authors.

Figure 1.1
Figure 1.1. Semistandard Young tableau A ∈ SSYT(4, 3, 2) and the correspond￾ing monomial x A = x 2 1 x 3 2 x3 x 3 4 . Λn are well defined.1 Littlewood–Richardson (LR) coefficients are now defined as: sµ · sν = X λ c λ µ,ν sλ . Schur polynomials encode fundamental symmetries in algebra and geometry. They are ubiqui￾tous in Enumerative and Algebraic Combinatorics [Ful97, Sta99], Representation Theory [Sag01], Algebraic Geometry [… view at source ↗
Figure 1.2
Figure 1.2. Graphs in RC(1432) and the corresponding Schubert polynomial S1432 = x1x2x3 + x 2 1x3 + x1x 2 2 + x 2 2x3 + x 2 1x2 with monomials in this order. The Schubert polynomial Sw ∈ N[x1, x2, . . .] is defined as (1.1) Sw(x) := X H ∈RC(w) x H where x H := Y (i,j) : H(i,j)=⊞ xi . In other words, x H is the product of xi ’s over all crosses (i, j) ∈ H, see [PITH_FULL_IMAGE:figures/full_fig_p003_1_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

113 extracted references · 50 canonical work pages

  1. [1]

    Scott Aaronson, and the polynomial hierarchy, in Proc.\ 42nd STOC (2010), 141--150

    2010

  2. [2]

    Scott Aaronson, ? = , in Open problems in mathematics, Springer, Cham, 2016, 1--122

    2016

  3. [3]

    Anshul Adve, Colleen Robichaux and Alexander Yong, Vanishing of Littlewood--Richardson polynomials is in , Comput.\ Complexity 28 (2019), 241--257

    2019

  4. [4]

    383 (2021), Paper No

    Anshul Adve, Colleen Robichaux and Alexander Yong, An efficient algorithm for deciding vanishing of Schubert polynomial coefficients, Adv.\ Math. 383 (2021), Paper No. 107669, 38 pp.; extended abstract in Proc.\ 31st FPSAC (2020), Art. 52, 12 pp

    2021

  5. [5]

    Rida Ait El Manssour, Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi and James Worrell, A parametric version of the Hilbert Nullstellensatz, preprint (2024), 13 pp.; extended abstract in Proc.\ 8th SOSA (2025), 444--451; arXiv:2408.13027

    arXiv 2024

  6. [6]

    David Anderson and William Fulton, Equivariant cohomology in algebraic geometry, Cambridge Univ.\ Press, Cambridge, UK, 2024, 446 pp

    2024

  7. [7]

    435 (2023), Paper No

    David Anderson, Takeshi Ikeda, Minyoung Jeon and Ryotaro Kawago, The multiplicity of a singularity in a vexillary S chubert variety, Adv.\ Math. 435 (2023), Paper No. 109366, 39 pp

    2023

  8. [8]

    214 (2007), 495--524

    Federico Ardila and Sara Billey, Flag arrangements and triangulations of products of simplices, Adv.\ Math. 214 (2007), 495--524

    2007

Show all 113 references
  1. [9]

    A modern approach, Cambridge Univ.\ Press, Cambridge, 2009, 579 pp

    Sanjeev Arora and Boaz Barak, Computational complexity. A modern approach, Cambridge Univ.\ Press, Cambridge, 2009, 579 pp

    2009

  2. [10]

    15 (2006), 133--173

    Prakash Belkale, Geometric proofs of H orn and saturation conjectures, J.\ Algebraic Geom. 15 (2006), 133--173

    2006

  3. [11]

    2 (1993), 257--269

    Nantel Bergeron and Sara Billey, RC-graphs and Schubert polynomials, Exp.\ Math. 2 (1993), 257--269

    1993

  4. [12]

    Sara Billey and Mark Haiman, Schubert polynomials for the classical groups, Jour.\ AMS 8 (1995), 443--482

    1995

  5. [13]

    Stanley, Some combinatorial properties of Schubert polynomials, J

    Sara Billey, William Jockusch and Richard P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), 345--374

    1993

  6. [14]

    Sara Billey and Ravi Vakil, Intersections of S chubert varieties and other permutation array schemes, in Algorithms in algebraic geometry, Springer, New York, 2008, 21--54

    2008

  7. [15]

    Markus Bl\"aser and Christian Ikenmeyer, Introduction to geometric complexity theory, preprint (2018), 148 pp.; to appear in Theory of Computing Graduate Surveys; available at tinyurl.com/mpan48e6 https://www.dcs.warwick.ac.uk/ u2270030/teaching_sb/summer17/introtogct/gct.pdf

    2018

  8. [16]

    Lenore Blum, Felipe Cucker, Mike Shub and Steve Smale, Complexity and real computation, Springer, New York, 1998, 453 pp

    1998

  9. [17]

    Lenore Blum, Mike Shub and Steve Smale, On a theory of computation and complexity over the real numbers: -completeness, recursive functions and universal machines, Bull.\ AMS 21 (1989), 1--46

    1989

  10. [18]

    Boppana, Johan Hastad and Stathis Zachos, Does have short interactive proofs?, Inform.\ Process.\ Lett

    Ravi B. Boppana, Johan Hastad and Stathis Zachos, Does have short interactive proofs?, Inform.\ Process.\ Lett. 25 (1987), 127--132

    1987

  11. [19]

    Peter Borwein, Stephen Choi, Brendan Rooney and Andrea Weirathmueller (Eds.), The Riemann hypothesis, Springer, New York, 2008, 533 pp

    2008

  12. [20]

    Emmanuel Briand, Rosa Orellana and Mercedes Rosas, Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH, Comput.\ Complexity 18 (2009), 577--600

    2009

  13. [21]

    Graham Brightwell and Peter Winkler, Counting linear extensions, Order 8 (1991), 225--247; extended abstract in Proc.\ 23rd STOC (1991), 175--181

    1991

  14. [22]

    Buch, Frank Sottile and Alexander Yong, Quiver coefficients are Schubert structure constants, Math.\ Res.\ Lett

    Anders S. Buch, Frank Sottile and Alexander Yong, Quiver coefficients are Schubert structure constants, Math.\ Res.\ Lett. 12 (2005), 567--574

    2005

  15. [23]

    010329, 12 pp.; extended abstract in Proc.\ 27th QIP (2024)

    Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojt e ch Havl\' c ek and Guanyu Zhu, Quantum complexity of the Kronecker coefficients, PRX Quantum 5 (2024), Paper No. 010329, 12 pp.; extended abstract in Proc.\ 27th QIP (2024)

    2024

  16. [24]

    Peter B\"urgisser and Felipe Cucker, Counting complexity classes for numeric computations. II . Algebraic and semialgebraic sets, J.\ Complexity 22 (2006), 147--191; extended abstract in Proc.\ 36th STOC (2004), 475--485

    2006

  17. [25]

    The geometry of numerical algorithms, Springer, Heidelberg, 2013, 554 pp

    Peter B\"urgisser and Felipe Cucker, Condition. The geometry of numerical algorithms, Springer, Heidelberg, 2013, 554 pp

    2013

  18. [26]

    27 (2013), 1639--1681; extended abstract in Proc.\ 21st FPSAC (2009), 267--278

    Peter B\"urgisser and Christian Ikenmeyer, Deciding positivity of Littlewood--Richardson coefficients, SIAM J.\ Discrete Math. 27 (2013), 1639--1681; extended abstract in Proc.\ 21st FPSAC (2009), 267--278

    2013

  19. [27]

    Peter B\"urgisser, Christian Ikenmeyer and Greta Panova, No occurrence obstructions in geometric complexity theory, Jour.\ AMS 32 (2019), 163--193; extended abstract in Proc.\ 57th FOCS (2016), 386--395

    2019

  20. [28]

    Pi 12 (2024), Paper No

    Swee Hong Chan and Igor Pak, Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy, Forum Math. Pi 12 (2024), Paper No. e21, 38 pp.; extended abstract in Proc.\ 56th STOC (2024), 875--883

    2024

  21. [29]

    1015 (2024), Paper No

    Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, Theoret.\ Comput.\ Sci. 1015 (2024), Paper No. 114776, 19 pp

    2024

  22. [30]

    Swee Hong Chan and Igor Pak, Equality cases of the Stanley--Yan log-concave matroid inequality, preprint (2024), 36 pp.; arXiv:2407.19608

    2024 arXiv

  23. [31]

    32:3, 47 pp.; extended abstract in Proc.\ 35th CCC (2020), 14:1--14:27

    Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She and Srikanth Srinivasan, Schur polynomials do not have small formulas if the determinant doesn't, Computational Complexity 32 (2023), Art. 32:3, 47 pp.; extended abstract in Proc.\ 35th CCC (2020)...

    2023

  24. [32]

    Matthias Christandl, Brent Doran and Michael Walter, Computing multiplicities of Lie group representations, in Proc.\ 53rd FOCS (2012), 639--648

    2012

  25. [33]

    De Loera and Tyrrell B

    Jes\'us A. De Loera and Tyrrell B. McAllister, On the computation of C lebsch-- G ordan coefficients and the dilation effect, Experiment.\ Math. 15 (2006), 7--19

    2006

  26. [34]

    25 (2000), 194--211

    Kimmo Eriksson and Svante Linusson, A combinatorial theory of higher-dimensional permutation arrays, Adv.\ in Appl.\ Math. 25 (2000), 194--211

    2000

  27. [35]

    25 (2000), 212--227

    Kimmo Eriksson and Svante Linusson, A decomposition of Fl (n)^d indexed by permutation arrays, Adv.\ in Appl.\ Math. 25 (2000), 212--227

    2000

  28. [36]

    Stephen Fenner, Frederic Green, Steven Homer and Randall Pruim, Quantum is hard for , in Theoretical computer science, World Sci., River Edge, NJ, 1998, 241--252

    1998

  29. [37]

    Stanley, Schubert polynomials and the nil-Coxeter algebra, Adv.\ Math

    Sergey Fomin and Richard P. Stanley, Schubert polynomials and the nil-Coxeter algebra, Adv.\ Math. 103 (1994), 196--207

    1994

  30. [38]

    William Fulton, Young tableaux, Cambridge Univ.\ Press, Cambridge, UK, 1997, 260 pp

    1997

  31. [39]

    21, 18629--18663

    Yibo Gao and Daoji Huang, The canonical bijection between pipe dreams and bumpless pipe dreams, Int.\ Math.\ Res.\ Notices 2023 (2023), no. 21, 18629--18663

    2023

  32. [40]

    Gasarch, The third =? poll, ACM SIGACT News 50 (2019), no

    William I. Gasarch, The third =? poll, ACM SIGACT News 50 (2019), no. 1, 38–59

    2019

  33. [41]

    A conceptual perspective, Cambridge Univ.\ Press, Cambridge, UK, 2008, 606 pp

    Oded Goldreich, Computational complexity. A conceptual perspective, Cambridge Univ.\ Press, Cambridge, UK, 2008, 606 pp

    2008

  34. [42]

    Andrew Hardt and David Wallach, When do Schubert polynomial products stabilize?, preprint (2024), 32 pp.; arXiv:2412.06976

    2024 arXiv

  35. [43]

    Hauenstein, Nickolas Hein and Frank Sottile, A primal-dual formulation for certifiable computations in Schubert calculus, Found.\ Comput.\ Math

    Jonathan D. Hauenstein, Nickolas Hein and Frank Sottile, A primal-dual formulation for certifiable computations in Schubert calculus, Found.\ Comput.\ Math. 16 (2016), 941--963

    2016

  36. [44]

    Symbolic Comput

    Nickolas Hein and Frank Sottile, A lifted square formulation for certifiable S chubert calculus, J. Symbolic Comput. 79 (2017), 594--608

    2017

  37. [45]

    thesis, Univ.\ of Calgary, 1994, 117 pp.; available at dspace.ucalgary.ca/handle/1880/45530 https://dspace.ucalgary.ca/handle/1880/45530

    Charels Hepler, On the complexity of computing characters of finite groups, Ph.D. thesis, Univ.\ of Calgary, 1994, 117 pp.; available at dspace.ucalgary.ca/handle/1880/45530 https://dspace.ucalgary.ca/handle/1880/45530

    1994

  38. [46]

    Mulmuley and Michael Walter, On vanishing of Kronecker coefficients, Comp.\ Complexity 26 (2017), 949--992

    Christian Ikenmeyer, Ketan D. Mulmuley and Michael Walter, On vanishing of Kronecker coefficients, Comp.\ Complexity 26 (2017), 949--992

    2017

  39. [47]

    Christian Ikenmeyer and Igor Pak, What is in and what is not?, preprint (2022), 82 pp.; extended abstract in Proc.\ 63rd FOCS (2022), 860--871; arXiv:2204.13149

    2022 arXiv

  40. [48]

    (2024), no

    Christian Ikenmeyer, Igor Pak and Greta Panova, Positivity of the symmetric group characters is as hard as the polynomial time hierarchy, Int.\ Math.\ Res.\ Not. (2024), no. 10, 8442--8458; extended abstract in Proc.\ 34th SODA (2023), 3573--3586

    2024

  41. [49]

    319 (2017), 40--66; extended abstract in Proc.\ 57th FOCS (2016), 396--405

    Christian Ikenmeyer and Greta Panova, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Adv.\ Math. 319 (2017), 40--66; extended abstract in Proc.\ 57th FOCS (2016), 396--405

    2017

  42. [50]

    Christian Ikenmeyer and Sathyawageeswar Subramanian, A remark on the quantum complexity of the Kronecker coefficients, preprint (2023), 13 pp.; arXiv:2307.02389 ; extended abstract in Proc.\ 27th QIP (2024)

    2023 arXiv

  43. [51]

    Russell Impagliazzo and Avi Wigderson, = if requires exponential circuits: derandomizing the XOR lemma, in Proc.\ 29th STOC (1997), 220-229

    1997

  44. [52]

    162 (2005), 1--17

    Zbigniew Jelonek, On the effective Nullstellensatz, Invent.\ Math. 162 (2005), 1--17

    2005

  45. [53]

    Kleiman, The transversality of a general translate, Compositio Math

    Steven L. Kleiman, The transversality of a general translate, Compositio Math. 28 (1974), 287--297

    1974

  46. [54]

    Klivans and Dieter van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, SIAM J.\ Comput

    Adam R. Klivans and Dieter van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, SIAM J.\ Comput. 31 (2002), 1501--1526; extended abstract in Proc.\ 31st STOC (1999), 659--667

    2002

  47. [55]

    10 (2001), 345--353

    Allen Knutson, Descent-cycling in S chubert calculus, Experiment.\ Math. 10 (2001), 345--353

    2001

  48. [56]

    71, Math.\ Soc.\ Japan, Tokyo, 2016, 185--209

    Allen Knutson, Schubert calculus and puzzles, in Adv.\ Stud.\ Pure Math. 71, Math.\ Soc.\ Japan, Tokyo, 2016, 185--209

    2016

  49. [57]

    VI, EMS Press, 4582--4605

    Allen Knutson, Schubert calculus and quiver varieties, in Proc.\ ICM (2022, virtual), Vol. VI, EMS Press, 4582--4605

    2022

  50. [58]

    161 (2005), 1245--1318

    Allen Knutson and Ezra Miller, Gr\"obner geometry of Schubert polynomials, Annals\ of Math. 161 (2005), 1245--1318

    2005

  51. [59]

    Allen Knutson and Paul Zinn-Justin, Schubert puzzles and integrability I: invariant trilinear forms, preprint (2017), 51 pp.; arXiv:1706.10019

    2017 arXiv

  52. [60]

    Allen Knutson and Paul Zinn-Justin, Schubert puzzles and integrability III: separated descents, preprint (2023), 42 pp.; arXiv:2306.13855

    2023 arXiv

  53. [61]

    AMS 12 (1999), 1055--1090

    Allen Knutson and Terence Tao, The honeycomb model of _n( ) tensor products I: Proof of the saturation conjecture, J. AMS 12 (1999), 1055--1090

    1999

  54. [62]

    (2009), Art

    Hirotada Kobayashi, Keiji Matsumoto and Tomoyuki Yamakami, Quantum Merlin--Arthur proof systems: are multiple Merlins more helpful to Arthur? Chic.\ J.\ Theoret.\ Comput.\ Sci. (2009), Art. 3, 19 pp.; extended abstract in Proc.\ 14th ISAAC (2003), 189--198

    2009

  55. [63]

    15, 765--782

    Mikhail Kogan, RC-graphs and a generalized Littlewood--Richardson rule, Int.\ Math.\ Res.\ Notices (2001), no. 15, 765--782

    2001

  56. [64]

    Pascal Koiran, Hilbert's Nullstellensatz is in the polynomial hierarchy, J.\ Complexity 12 (1996), 273--286; see also DIMACS Tech.\ Report 96-27 (1996), 18 pp

    1996

  57. [65]

    54 (1997), no

    Pascal Koiran, A weak version of the B lum, S hub, and S male model, J.\ Comput.\ System Sci. 54 (1997), no. 1, part 2, 177--189; extended abstract in Proc.\ 34th FOCS (1993), 486--495

    1997

  58. [66]

    J\'anos Koll\'ar, Sharp effective Nullstellensatz, Jour.\ AMS 1 (1988), 963--975

    1988

  59. [67]

    Teresa Krick, Luis Miguel Pardo and Mart\' n Sombra, Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J. 109 (2001), 521--598

    2001

  60. [68]

    Lee and Mark Shimozono, Back stable Schubert calculus, Compositio Math

    Thomas Lam, Seung J. Lee and Mark Shimozono, Back stable Schubert calculus, Compositio Math. 157 (2021), 883--962

    2021

  61. [69]

    139 (1995), 303--317

    Alain Lascoux, Polyn\^ o mes de Schubert: une approche historique (in French), Discrete Math. 139 (1995), 303--317

    1995

  62. [70]

    R.\ Acad.\ Sci.\ Paris S\' er I, Math

    Alain Lascoux and Marcel-Paul Sch\" u tzenberger, Polyn\^ o mes de Schubert (in French), C. R.\ Acad.\ Sci.\ Paris S\' er I, Math. 294 (1982), 447--450

    1982

  63. [71]

    10 (1985), 111--124

    Alain Lascoux and Marcel-Paul Sch\" u tzenberger, Schubert polynomials and the Littlewood--Richardson rule, Lett.\ Math.\ Phys. 10 (1985), 111--124

    1985

  64. [72]

    90 (2021), 1407--1433

    Anton Leykin, Abraham Martín del Campo, Frank Sottile, Ravi Vakil and Jan Verschelde, Numerical Schubert calculus via the Littlewood--Richardson homotopy algorithm, Math.\ Comp. 90 (2021), 1407--1433

    2021

  65. [73]

    Ian G. Macdonald, Notes on Schubert polynomials, Publ.\ LaCIM, UQAM, Montreal, 1991, 116 pp.; available at tinyurl.com/382f7an7 http://www.math.uwaterloo.ca/ opecheni/macdonaldschubert.pdf

    1991

  66. [74]

    Macdonald, Symmetric functions and Hall polynomials (Second ed.), Oxford U

    Ian G. Macdonald, Symmetric functions and Hall polynomials (Second ed.), Oxford U. Press, New York, 1995, 475 pp

    1995

  67. [75]

    Gunter Malle and Donna Testerman, Linear algebraic groups and finite groups of Lie type, Cambridge Univ.\ Press, Cambridge, UK, 2011, 309 pp

    2011

  68. [76]

    Laurent Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS, Providence, RI, 2001, 167 pp

    2001

  69. [77]

    Mayr and Albert R

    Ernst W. Mayr and Albert R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv.\ Math. 46 (1982), 305--329

    1982

  70. [78]

    Karola M\'esz\'aros, Greta Panova and Alexander Postnikov, Schur times Schubert via the Fomin--Kirillov algebra, Electron.\ J. Combin. 21 (2014), no. 1, Paper 1.39, 22 pp

    2014

  71. [79]

    Miltersen and N

    Peter B. Miltersen and N. Variyam Vinodchandran, Derandomizing Arthur--Merlin games using hitting sets, Comput.\ Complexity 14 (2005), 256--279; extended abstract in Proc.\ 4th FOCS (1999), 71--80

    2005

  72. [80]

    Priyanka Mukhopadhyay and Youming Qiao, Sparse multivariate polynomial interpolation on the basis of Schubert polynomials, Comput.\ Complexity 26 (2017), 881--909

    2017

  73. [81]

    Ketan D. Mulmuley, Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry, preprint (2009, v4), 139 pp.; arXiv: 0704.0229

    2009 arXiv

  74. [82]

    Mulmuley, Hariharan Narayanan and Milind Sohoni, Geometric complexity theory III

    Ketan D. Mulmuley, Hariharan Narayanan and Milind Sohoni, Geometric complexity theory III. On deciding nonvanishing of a Littlewood--Richardson coefficient, J.\ Algebraic Combin. 36 (2012), 103--110

    2012

  75. [83]

    Algebraic Combin

    Hariharan Narayanan, On the complexity of computing Kostka numbers and Littlewood--Richardson coefficients, J. Algebraic Combin. 24 (2006), 347--354

    2006

  76. [84]

    387 (2021), 1--75; extended abstract in Proc.\ 47th STOC (2015), 529--538

    Ryan O'Donnell and John Wright, Quantum spectrum testing, Comm.\ Math.\ Phys. 387 (2021), 1--75; extended abstract in Proc.\ 47th STOC (2015), 529--538

    2021

  77. [85]

    Igor Pak, What is a combinatorial interpretation?, in Open Problems in Algebraic Combinatorics, AMS, Providence, RI, 2024, 191--260

    2024

  78. [86]

    Igor Pak and Greta Panova, On the complexity of computing Kronecker coefficients, Comput.\ Complexity 26 (2017), 1--36

    2017

  79. [87]

    Igor Pak and Greta Panova, Breaking down the reduced Kronecker coefficients, C. R. Math.\ Acad.\ Sci.\ Paris 358 (2020), no. 4, 463--468

    2020

  80. [88]

    Igor Pak and Colleen Robichaux, Signed combinatorial interpretations in algebraic combinatorics, preprint (2024), 24 pp.; to appear in Algebraic Combinatorics; arXiv:2406.13902

    2024 arXiv

  81. [89]

    Igor Pak and Colleen Robichaux, the first version of this preprint (2024), 24 pp.; arXiv:2412.02064v1

    2024 arXiv

  82. [90]

    Igor Pak and Colleen Robichaux, Positivity of Schubert coefficients, preprint, 7 pp.; arXiv:2412.18984

    arXiv

  83. [91]

    Greta Panova, Computational complexity in algebraic combinatorics, to appear in Current Developments in Mathematics, International Press, Boston, MA, 30 pp.; arXiv:2306.17511

    arXiv

  84. [92]

    Greta Panova, Complexity and asymptotics of structure constants, in Open Problems in Algebraic Combinatorics, AMS, Providence, RI, 2024, 61--86

    2024

  85. [93]

    Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994, 523 pp

    Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994, 523 pp

    1994

  86. [94]

    e114, 24 pp

    Oliver Pechenik and Anna Weigandt, An inverse Grassmannian Littlewood--Richardson rule and extensions, Forum Math.\ Sigma 12 (2024), Paper No. e114, 24 pp

    2024

  87. [95]

    Stanley, Chains in the Bruhat order, J.\ Algebraic Combin

    Alexander Postnikov and Richard P. Stanley, Chains in the Bruhat order, J.\ Algebraic Combin. 29 (2009), 133--174

    2009

  88. [96]

    Kevin Purbhoo, Vanishing and non-vanishing criteria for branching S chubert calculus , Ph.D.\ thesis, UC Berkeley, 2004, 96 pp

    2004

  89. [97]

    24590, 38 pp

    Kevin Purbhoo, Vanishing and nonvanishing criteria in Schubert calculus, Int.\ Math.\ Res.\ Notices 2006 (2006), Art. 24590, 38 pp

    2006

  90. [98]

    ACM 69 (2022), no

    Ran Raz and Avishay Tal, Oracle separation of and , Jour. ACM 69 (2022), no. 4, Art. 30, 21 pp.; extended abstract in Proc.\ 51st STOC (2019), 13--23

    2022

  91. [99]

    Maurice Rojas, Efficiently detecting torsion points and subtori, in Contemp.\ Math

    J. Maurice Rojas, Efficiently detecting torsion points and subtori, in Contemp.\ Math. 448, AMS, Providence, RI, 2007, 215--235

    2007

  92. [100]

    Sagan, The symmetric group, Springer, New York, 2001, 238 pp

    Bruce E. Sagan, The symmetric group, Springer, New York, 2001, 238 pp

    2001

  93. [101]

    5849, Springer, Berlin, 2010, 334--344

    Marcus Schaefer, Complexity of some geometric and topological problems, in Lecture Notes Comput.\ Sci. 5849, Springer, Berlin, 2010, 334--344

    2010

  94. [102]

    231 (2023), 89--204

    Yair Shenfeld and Ramon van Handel, The extremals of the Alexandrov--Fenchel inequality for convex polytopes, Acta Math. 231 (2023), 89--204

    2023

  95. [103]

    5 (2009), 207--388

    Amir Shpilka and Amir Yehudayoff, Arithmetic circuits: a survey of recent results and open questions, Found.\ Trends Theor.\ Comput.\ Sci. 5 (2009), 207--388

    2009

  96. [104]

    107 (2023), Paper No

    Evgeny Smirnov and Anna Tutubalina, Pipe dreams for Schubert polynomials of the classical groups, European J.\ Combin. 107 (2023), Paper No. 103613, 46 pp

    2023

  97. [105]

    Searles, Root-theoretic Young diagrams and Schubert calculus, Ph.D.\ thesis, UIUC, 2015, 89 pp

    Dominic N. Searles, Root-theoretic Young diagrams and Schubert calculus, Ph.D.\ thesis, UIUC, 2015, 89 pp

    2015

  98. [106]

    Dizier and Alexander Yong, Generalized permutahedra and S chubert calculus, Arnold Math

    Avery St. Dizier and Alexander Yong, Generalized permutahedra and S chubert calculus, Arnold Math. J. 8 (2022), 517--533

    2022

  99. [107]

    Stanley, Two combinatorial applications of the Aleksandrov--Fenchel inequalities, J.\ Combin.\ Theory, Ser

    Richard P. Stanley, Two combinatorial applications of the Aleksandrov--Fenchel inequalities, J.\ Combin.\ Theory, Ser. A 31 (1981), 56--65

    1981

  100. [108]

    Stanley, Enumerative Combinatorics , vol

    Richard P. Stanley, Enumerative Combinatorics , vol. 1 (Second ed.) and vol. 2, Cambridge Univ. Press, 2012 and 1999, 626 pp.\ and 581 pp

    2012

  101. [109]

    Stanley, Positivity problems and conjectures in algebraic combinatorics, in Mathematics: frontiers and perspectives, AMS, Providence, RI, 2000, 295--319

    Richard P. Stanley, Positivity problems and conjectures in algebraic combinatorics, in Mathematics: frontiers and perspectives, AMS, Providence, RI, 2000, 295--319

    2000

  102. [110]

    Jun Tarui, Randomized polynomials, threshold circuits, and the polynomial hierarchy, in Proc.\ 8th STACS (1991), 238--250

    1991

  103. [111]

    Hermann Weyl, The Classical Groups: Their Invariants and Representations, Princeton Univ.\ Press, Princeton, NJ, 1939, 302 pp

    1939

  104. [112]

    Avi Wigderson, Mathematics and computation, Princeton Univ.\ Press, Princeton, NJ, 2019, 418 pp

    2019

  105. [113]

    2, Plenary lectures, EMS Press, Berlin, 2023, 1392--1432

    Avi Wigderson, Interactions of computational complexity theory and mathematics, in Proc.\ ICM 2022, Vol. 2, Plenary lectures, EMS Press, Berlin, 2023, 1392--1432

    2022

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.