论文标题
关于评估最高权重向量的复杂性
On the complexity of evaluating highest weight vectors
论文作者
论文摘要
几何复杂性理论（GCT）是通过代数几何和表示理论分离代数复杂性类别的一种方法。最初提出的Mulmuley和Sohoni（Siam J Comput 2001，2008）使用发生障碍物证明Valiant的决定因素与永久性猜想，但最近Bürgisser，Ikenmeyer和Panova（AMS 2019杂志）证明这是不可能的。但是，代数几何学和表示理论的基本定理可以通过使用所谓的最高权重矢量（HWV）来证明GCT中的每个下限。在对GCT感兴趣的环境中（即在多项式的情况下），我们证明了对HWV的评估的NP硬度，如果相应的Young-Diagram的树宽度很小，则将提供有效的算法，如果评估点很小，在该较小的情况下，将其作为非公认的Algebraic Algebraic Algebraic分支程序！特别是，这提供了一个很大的新类别分离功能，可以在低（边界）战争等级的点上有效评估。
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 so-called highest weight vectors (HWVs). In the setting of interest in GCT (namely in the setting of polynomials) we prove the NP-hardness of the evaluation of HWVs in general, and we give efficient algorithms if the treewidth of the corresponding Young-diagram 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.
