English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  On semiring complexity of Schur polynomials

Fomin, S., Grigoriev, D., Nogneng, D., & Schost, E. (2018). On semiring complexity of Schur polynomials. Computational Complexity, 27(4), 595-616. doi:10.1007/s00037-018-0169-3.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/21.11116/0000-0003-FD47-1 Version Permalink: https://hdl.handle.net/21.11116/0000-0004-44A0-A
Genre: Journal Article

Files

show Files
hide Files
:
arXiv:1608.05043.pdf (Preprint), 239KB
View   Save
File Permalink:
https://hdl.handle.net/21.11116/0000-0003-FD49-F
Name:
arXiv:1608.05043.pdf
Description:
File downloaded from arXiv at 2019-07-08 13:49
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://arxiv.org/licenses/nonexclusive-distrib/1.0/
:
Fomin-Grigoriev_Nogneng-Schost_On semiring complexity of schur polynominals_2018.pdf (Publisher version), 401KB
 
File Permalink:
-
Name:
Fomin-Grigoriev_Nogneng-Schost_On semiring complexity of schur polynominals_2018.pdf
Description:
-
OA-Status:
Visibility:
Restricted ( Max Planck Society (every institute); )
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show
hide
Locator:
https://doi.org/10.1007/s00037-018-0169-3 (Publisher version)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Fomin, Sergey, Author
Grigoriev, Dima1, Author           
Nogneng, Dorian, Author
Schost, Eric, Author
Affiliations:
1Max Planck Institute for Mathematics, Max Planck Society, ou_3029201              

Content

show
hide
Free keywords: Computer Science, Computational Complexity, Mathematics, Combinatorics
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2018
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: arXiv: 1608.05043
arXiv: http://arxiv.org/abs/1608.05043
DOI: 10.1007/s00037-018-0169-3
Other: http://www.mpim-bonn.mpg.de/preblob/5652
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Computational Complexity
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 27 (4) Sequence Number: - Start / End Page: 595 - 616 Identifier: -