Computational Complexity, volume 27, issue 4, pages 595-616
On semiring complexity of Schur polynomials
Sergey Fomin
1
,
Dima Grigoriev
2
,
Dorian Nogneng
3
,
Éric Schost
4
3
LIX, École Polytechnique, Palaiseau Cedex, France
|
Publication type: Journal Article
Publication date: 2018-06-04
Journal:
Computational Complexity
scimago Q2
SJR: 0.453
CiteScore: 1.5
Impact factor: 0.7
ISSN: 10163328, 14208954
General Mathematics
Computational Mathematics
Computational Theory and Mathematics
Theoretical Computer Science
Abstract
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.
Found
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.