Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeometric Complexity Theory VII: Nonstandard quantum group for the plethysm problem
135
0
0.0
(
0
)
Added by
Ketan Mulmuley D
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Ketan D. Mulmuley
Ask ChatGPT about the research
No Arabic abstract
This article describes a {em nonstandard} quantum group that may be used to derive a positive formula for the plethysm problem, just as the standard (Drinfeld-Jimbo) quantum group can be used to derive the positive Littlewood-Richardson rule for arbitrary complex semisimple Lie groups. The sequel cite{GCT8} gives conjecturally correct algorithms to construct canonical bases of the coordinate rings of these nonstandard quantum groups and canonical bases of the dually paired nonstandard deformations of the symmetric group algebra. A positive $#P$-formula for the plethysm constant follows from the conjectural properties of these canonical bases and the duality and reciprocity conjectures herein.
rate research
Read More
This article gives conjecturally correct algorithms to construct canonical bases of the irreducible polynomial representations and the matrix coordinate rings of the nonstandard quantum groups in GCT4 and GCT7, and canonical bases of the dually paired nonstandard deformations of the symmetric group algebra therein. These are generalizations of the canonical bases of the irreducible polynomial representations and the matrix coordinate ring of the standard quantum group, as constructed by Kashiwara and Lusztig, and the Kazhdan-Lusztig basis of the Hecke algebra. A positive ($#P$-) formula for the well-known plethysm constants follows from their conjectural properties and the duality and reciprocity conjectures in cite{GCT7}.
In two papers, Burgisser and Ikenmeyer (STOC 2011, STOC 2013) used an adaption of the geometric complexity theory (GCT) approach by Mulmuley and Sohoni (Siam J Comput 2001, 2008) to prove lower bounds on the border rank of the matrix multiplication tensor. A key ingredient was information about certain Kronecker coefficients. While tensors are an interesting test bed for GCT ideas, the far-away goal is the separation of algebraic complexity classes. The role of the Kronecker coefficients in that setting is taken by the so-called plethysm coefficients: These are the multiplicities in the coordinate rings of spaces of polynomials. Even though several hardness results for Kronecker coefficients are known, there are almost no results about the complexity of computing the plethysm coefficients or even deciding their positivity. In this paper we show that deciding positivity of plethysm coefficients is NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both problems remain hard even if the inner parameter of the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed, then the plethysm coefficient can be computed in polynomial time. Moreover, we derive new lower and upper bounds and in special cases even combinatorial descriptions for plethysm coefficients, which we consider to be of independent interest. Our technique uses discrete tomography in a more refined way than the recent work on Kronecker coefficients by Ikenmeyer, Mulmuley, and Walter (Comput Compl 2017). This makes our work the first to apply techniques from discrete tomography to the study of plethysm coefficients. Quite surprisingly, that interpretation also leads to new equalities between certain plethysm coefficients and Kronecker coefficients.
These are lectures notes for the introductory graduate courses on geometric complexity theory (GCT) in the computer science department, the university of Chicago. Part I consists of the lecture notes for the course given by the first author in the spring quarter, 2007. It gives introduction to the basic structure of GCT. Part II consists of the lecture notes for the course given by the second author in the spring quarter, 2003. It gives introduction to invariant theory with a view towards GCT. No background in algebraic geometry or representation theory is assumed. These lecture notes in conjunction with the article cite{GCTflip1}, which describes in detail the basic plan of GCT based on the principle called the flip, should provide a high level picture of GCT assuming familiarity with only basic notions of algebra, such as groups, rings, fields etc.
We study a basic algorithmic problem in algebraic geometry, which we call NNL, of constructing a normalizing map as per Noethers Normalization Lemma. For general explicit varieties, as formally defined in this paper, we give a randomized polynomial-time Monte Carlo algorithm for this problem. For some interesting cases of explicit varieties, we give deterministic quasi-polynomial time algorithms. These may be contrasted with the standard EXPSPACE-algorithms for these problems in computational algebraic geometry. In particular, we show that: (1) The categorical quotient for any finite dimensional representation $V$ of $SL_m$, with constant $m$, is explicit in characteristic zero. (2) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in the dimension of $V$. (3) The categorical quotient of the space of $r$-tuples of $m times m$ matrices by the simultaneous conjugation action of $SL_m$ is explicit in any characteristic. (4) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in $m$ and $r$ in any characteristic $p$ not in $[2, m/2]$. (5) NNL for every explicit variety in zero or large enough characteristic can be solved deterministically in quasi-polynomial time, assuming the hardness hypothesis for the permanent in geometric complexity theory. The last result leads to a geometric complexity theory approach to put NNL for every explicit variety in P.
Geometric complexity theory (GCT) is an approach to the P vs. NP and related problems. This article gives its complexity theoretic overview without assuming any background in algebraic geometry or representation theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
