Record Details

Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient
 
Creator MULMULEY, KD
NARAYANAN, H
SOHONI, M
 
Subject Littlewood-Richardon coefficients
Geometric complexity theory
Algorithms
POLYNOMIAL ALGORITHM
SATURATION
MODEL
 
Description We point out that the positivity of a Littlewood-Richardson coefficient for sl (n) can be decided in strongly polynomial time. This means that the number of arithmetic operations is polynomial in n and independent of the bit lengths of the specifications of the partitions alpha,beta, and gamma, and each operation involves numbers whose bitlength is polynomial in n and the bit lengths alpha,beta, and gamma. Secondly, we observe that nonvanishing of a generalized Littlewood-Richardson coefficient of any type can be decided in strongly polynomial time assuming an analogue of the saturation conjecture for these types, and that for weights alpha,beta,gamma, the positivity of can (unconditionally) be decided in strongly polynomial time.
 
Publisher SPRINGER
 
Date 2014-10-15T15:06:39Z
2014-10-15T15:06:39Z
2012
 
Type Article
 
Identifier JOURNAL OF ALGEBRAIC COMBINATORICS, 36(1)103-110
http://dx.doi.org/10.1007/s10801-011-0325-1
http://dspace.library.iitb.ac.in/jspui/handle/100/15116
 
Language en