On semiring complexity of Schur polynomials
Tóm tắt
Semiring complexity is the version of arithmetic circuit complexity that allows only two operations: addition and multiplication. We show that semiring complexity of a Schur polynomial
$${s_\lambda(x_1,\dots,x_k)}$$
labeled by a partition
$${\lambda=(\lambda_1\ge\lambda_2\ge\cdots)}$$
is bounded by
$${O(\log(\lambda_1))}$$
provided the number of variables k is fixed.
Tài liệu tham khảo
Anders Björner, Michelle Wachs (1982) Bruhat order of Coxeter groups and shellability. Adv. in Math. 43(1): 87–100
Anders Björner, Michelle L. Wachs (1988) Generalized quotients in Coxeter groups. Trans. Amer. Math. Soc. 308(1): 1–37
Cy P. Chan, Vesselin Drensky, Alan Edelman, Raymond Kan & Plamen Koev (2008). On computing Schur functions and series thereof, preprint.
James Demmel, Plamen Koev (2006) Accurate and efficient evaluation of Schur and Jack functions. Math. Comp. 75(253): 223–239
Sergey Fomin, Dima Grigoriev, Gleb Koshevoy (2016) Subtraction-free complexity, cluster transformations, and spanning trees. Found. Comput. Math. 16(1): 1–31
Dima Grigoriev, Gleb Koshevoy (2016) Complexity of tropical Schur polynomials. J. Symbolic Comput. 74: 46–54
Mark Jerrum, Marc Snir (1982) Some exact complexity results for straight-line computations over semirings. J. Assoc. Comput. Mach. 29(3): 874–897
Plamen Koev (2007) Accurate computations with totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 29(3): 731–751
Ian G. Macdonald (2015). Symmetric functions and Hall polynomials. Oxford University Press, New York, 2nd edition.
Hariharan Narayanan (2006) On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients. J. Algebraic Combin. 24(3): 347–354
Robert A. Proctor (1982) Classical Bruhat orders and lexicographic shellability. J. Algebra 77(1): 104–126
Claus-Peter Schnorr (1976) A lower bound on the number of additions in monotone computations. Theoret. Comput. Sci. 2(3): 305–315
Eli Shamir & Marc Snir (1977). Lower bounds on the number of multiplications and the number of additions in monotone computations. Technical Report RC-6757, IBM.
Richard P. Stanley (1999) Enumerative combinatorics. Vol. 2. Cambridge University Press, Cambridge
Volker Strassen (1972/73). Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math. 20, 238–251.
Volker Strassen (1973) Vermeidung von Divisionen. J. Reine Angew. Math. 264: 184–202
Leslie G. Valiant (1980) Negation can be exponentially powerful. Theoret. Comput. Sci. 12(3): 303–314
Michelle L. Wachs (2007). Poset topology: tools and applications. In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., 497–615. Amer. Math. Soc., Providence, RI.