Abstract-For fast kompakt ansluten Lie grupper H  på G, ger vi en polynom tid algoritm för att beräkna mångfalden av en given irreducible representation av H i begränsningen av en irreducible representation av G. Vår algoritm är baserad på en ändlig skillnad formel som gör multiplicities amenible till Barvinok algoritm för att räkna integral punkter i polytoper. Kroneckerkoefficienterna i den symmetriska gruppen, som kan ses som ett specialfall av sådana multipliciteter, spelar en viktig roll i den geometriska komplexitetsteorin förhållningssätt till P kontra NP-problemet. Medan deras beräkning är känd för att vara #P-hard för Young diagram med ett godtyckligt antal rader, beräknar vår algoritm dem i polynom tid om antalet rader begränsas. Vi kompletterar vårt arbete genom att visa att information om asymptotiska tillväxthastigheter av multipliciteter i koordinatringarna av omloppsbana stängningar inte direkt leder till nya komplexitet-teoretiska hinder utöver vad som kan erhållas från ögonblicket polytoper av omloppsbanan stängningar. Nonasymptotic information om multipliciteter, såsom tillhandahålls av vår algoritm, kan därför vara nödvändig för att hitta hinder i geometrisk komplexitet teori.
Till exempel, om antalet rader av alla parametrar är konstant, då Kronecker koefficienten kan beräknas i polynom tid REF.
Computing Multiplicities of Lie Group Representations
{'venue': "Proceedings of 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS'12), p. 639-648", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}