Bläser, Markus ;
Dörfler, Julian ;
Ikenmeyer, Christian
On the Complexity of Evaluating Highest Weight Vectors
Abstract
Geometric complexity theory (GCT) is an approach towards separating algebraic complexity classes through algebraic geometry and representation theory. Originally Mulmuley and Sohoni proposed (SIAM J Comput 2001, 2008) to use occurrence obstructions to prove Valiant’s determinant vs permanent conjecture, but recently Bürgisser, Ikenmeyer, and Panova (Journal of the AMS 2019) proved this impossible. However, fundamental theorems of algebraic geometry and representation theory grant that every lower bound in GCT can be proved by the use of socalled highest weight vectors (HWVs). In the setting of interest in GCT (namely in the setting of polynomials) we prove the NPhardness of the evaluation of HWVs in general, and we give efficient algorithms if the treewidth of the corresponding Youngtableau is small, where the point of evaluation is concisely encoded as a noncommutative algebraic branching program! In particular, this gives a large new class of separating functions that can be efficiently evaluated at points with low (border) Waring rank. As a structural side result we prove that border Waring rank is bounded from above by the ABP width complexity.
BibTeX  Entry
@InProceedings{blaser_et_al:LIPIcs.CCC.2021.29,
author = {Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Ikenmeyer, Christian},
title = {{On the Complexity of Evaluating Highest Weight Vectors}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {29:129:36},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14303},
URN = {urn:nbn:de:0030drops143036},
doi = {10.4230/LIPIcs.CCC.2021.29},
annote = {Keywords: Algebraic complexity theory, geometric complexity theory, algebraic branching program, Waring rank, border Waring rank, representation theory, highest weight vector, treewidth}
}
08.07.2021
Keywords: 

Algebraic complexity theory, geometric complexity theory, algebraic branching program, Waring rank, border Waring rank, representation theory, highest weight vector, treewidth 
Seminar: 

36th Computational Complexity Conference (CCC 2021)

Issue date: 

2021 
Date of publication: 

08.07.2021 