Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeometric Complexity Theory V: On deciding nonvanishing of a generalized Littlewood-Richardson coefficient
198
0
0.0
(
0
)
Added by
Ketan Mulmuley D
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This article has been withdrawn because it has been merged with the earlier article GCT3 (arXiv: CS/0501076 [cs.CC]) in the series. The merged article is now available as: Geometric Complexity Theory III: on deciding nonvanishing of a Littlewood-Richardson Coefficient, Journal of Algebraic Combinatorics, vol. 36, issue 1, 2012, pp. 103-110. (Authors: Ketan Mulmuley, Hari Narayanan and Milind Sohoni) The new article in this GCT5 slot in the series is: Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noethers Normalization Lemma, in the Proceedings of FOCS 2012 (abstract), arXiv:1209.5993 [cs.CC] (full version) (Author: Ketan Mulmuley)
rate research
Read More
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.
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.
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.
Geometric complexity theory (GCT) is an approach to the $P$ vs. $NP$ and related problems. A high level overview of this research plan and the results obtained so far was presented in a series of three lectures in the Institute of Advanced study, Princeton, Feb 9-11, 2009. This article contains the material covered in those lectures after some revision, and gives a mathematical overview of GCT. No background in algebraic geometry, representation theory or quantum groups is assumed.
We introduce a family of rings of symmetric functions depending on an infinite sequence of parameters. A distinguished basis of such a ring is comprised by analogues of the Schur functions. The corresponding structure coefficients are polynomials in
the parameters which we call the Littlewood-Richardson polynomials. We give a combinatorial rule for their calculation by modifying an earlier result of B. Sagan and the author. The new rule provides a formula for these polynomials which is manifestly positive in the sense of W. Graham. We apply this formula for the calculation of the product of equivariant Schubert classes on Grassmannians which implies a stability property of the structure coefficients. The first manifestly positive formula for such an expansion was given by A. Knutson and T. Tao by using combinatorics of puzzles while the stability property was not apparent from that formula. We also use the Littlewood-Richardson polynomials to describe the multiplication rule in the algebra of the Casimir elements for the general linear Lie algebra in the basis of the quantum immanants constructed by A. Okounkov and G. Olshanski.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
