Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient
Ketan D. Mulmuley1
, Hariharan Narayanan2
and Milind Sohoni3
1Department of Computer Science, University of Chicago, 1100 E 58th Street, Chicago, IL 60637, USA
2Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA
3Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, 400 076 India
2Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA
3Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, 400 076 India
DOI: 10.1007/s10801-011-0325-1
Abstract
We point out that the positivity of a Littlewood-Richardson coefficient _boxclose_boxclose_, c^{γ}_{α, β} for sl n can be decided in strongly polynomial time. This means that the number of arithmetic operations is polynomial in n and independent of the bit lengths of the specifications of the partitions α , β , and γ , and each operation involves numbers whose bitlength is polynomial in n and the bit lengths α , β , and γ .
Pages: 103–110
Keywords: keywords Littlewood-richardon coefficients; geometric complexity theory; algorithms
Full Text: PDF
References
1. Berenstein, A.D., Zelevinsky, A.V.: Tensor product multiplicities, canonical bases and totally positive varieties. Invent. Math. 143(1), 77-128 (2001)
2. Belkale, P., Kumar, S.: Eigencone, saturation and Horn problems for symplectic and odd orthogonal groups. J. Algebr. Geom. 19, 199-242 (2010)
3. Bürgisser, P., Ikenmeyer, C.: A max-flow algorithm for positivity of Littlewood-Richardson coefficients. In: FPSAC (2009)
4. Fulton, W., Harris, J.: Representation Theory. Springer, Berlin (1991)
5. Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8(4), 499-507 (1979)
6. Kapovich, M., Millson, J.: A path model for geodesics in Euclidean buildings and its applications to representation theory. Groups, Geom. Dyn. 2, 405-480 (2008)
7. Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373- 395 (1984)
8. Khachian, L.G.: A polynomial algorithm for linear programming. Dokl. Akad. Nauk SSSR 244, 1093-1096 (1979). (In Russian)
9. King, R.C., Tollu, C., Toumazet, F.: Stretched Littlewood-Richardson polynomials and Kostka coefficients. In: CRM Proceedings and Lecture Notes, vol. 34 (2003)
10. Knutson, A., Tao, T.: The honeycomb model of GLn(C) tensor products I: proof of the saturation conjecture. J. Am. Math. Soc. 12, 1055-1090 (1999)
11. Knutson, A., Tao, T.: Honeycombs and sums of Hermitian matrices. Not. Am. Math. Soc. 48(2), 175-186 (2001)
12. De Loera, J., McAllister, T.: On the computation of Clebsch-Gordan coefficients and the dilation effect. Exp. Math. 15(1), 7-20 (2006)
13. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1993)
14. Mulmuley, K.: On P vs. NP and geometric complexity theory. JACM 58(2) (2011)
15. Mulmuley, K., Sohoni, M.: Geometric complexity theory: an approach to the P vs. NP and related problems. SIAM J. Comput. 31(2), 496-526 (2001)
16. Mulmuley, K., Sohoni, M.: Geometric complexity theory II: towards explicit obstructions for embeddings among class varieties. SIAM J. Comput. 38(3) (2008)
17. Mulmuley, K., Sohoni, M.: Geometric complexity theory III, on deciding positivity of Littlewood- Richardson coefficients. Preprint (26 January 2005)
18. Mulmuley, K., Narayanan, H.: Geometric complexity theory V, on deciding non-vanishing of a generalized Littlewood-Richardson coefficients. Technical Report TR-2007-05, Computer Science De- partment, University of Chicago (April 2007)
19. Mulmuley, K.: Geometric complexity theory VI: the flip via positivity. Technical Report, Computer Science Department, The University of Chicago (January 2011). Available at:
20. Sam, S.: Symmetric quivers, invariant theory, and saturation theorems for the classical groups. (September, 2010)
21. Sturmfels, B.: On vector partition functions. J. Comb. Theory Ser. A 72(2) (1995)
22. Tardos, É.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250-256 (1986)
23. Valiant, L.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189-201 (1979)
24. Zelevinsky, A.: Littlewood-Richardson semigroups, new perspectives in geometric combinatorics.
2. Belkale, P., Kumar, S.: Eigencone, saturation and Horn problems for symplectic and odd orthogonal groups. J. Algebr. Geom. 19, 199-242 (2010)
3. Bürgisser, P., Ikenmeyer, C.: A max-flow algorithm for positivity of Littlewood-Richardson coefficients. In: FPSAC (2009)
4. Fulton, W., Harris, J.: Representation Theory. Springer, Berlin (1991)
5. Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8(4), 499-507 (1979)
6. Kapovich, M., Millson, J.: A path model for geodesics in Euclidean buildings and its applications to representation theory. Groups, Geom. Dyn. 2, 405-480 (2008)
7. Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373- 395 (1984)
8. Khachian, L.G.: A polynomial algorithm for linear programming. Dokl. Akad. Nauk SSSR 244, 1093-1096 (1979). (In Russian)
9. King, R.C., Tollu, C., Toumazet, F.: Stretched Littlewood-Richardson polynomials and Kostka coefficients. In: CRM Proceedings and Lecture Notes, vol. 34 (2003)
10. Knutson, A., Tao, T.: The honeycomb model of GLn(C) tensor products I: proof of the saturation conjecture. J. Am. Math. Soc. 12, 1055-1090 (1999)
11. Knutson, A., Tao, T.: Honeycombs and sums of Hermitian matrices. Not. Am. Math. Soc. 48(2), 175-186 (2001)
12. De Loera, J., McAllister, T.: On the computation of Clebsch-Gordan coefficients and the dilation effect. Exp. Math. 15(1), 7-20 (2006)
13. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1993)
14. Mulmuley, K.: On P vs. NP and geometric complexity theory. JACM 58(2) (2011)
15. Mulmuley, K., Sohoni, M.: Geometric complexity theory: an approach to the P vs. NP and related problems. SIAM J. Comput. 31(2), 496-526 (2001)
16. Mulmuley, K., Sohoni, M.: Geometric complexity theory II: towards explicit obstructions for embeddings among class varieties. SIAM J. Comput. 38(3) (2008)
17. Mulmuley, K., Sohoni, M.: Geometric complexity theory III, on deciding positivity of Littlewood- Richardson coefficients. Preprint (26 January 2005)
18. Mulmuley, K., Narayanan, H.: Geometric complexity theory V, on deciding non-vanishing of a generalized Littlewood-Richardson coefficients. Technical Report TR-2007-05, Computer Science De- partment, University of Chicago (April 2007)
19. Mulmuley, K.: Geometric complexity theory VI: the flip via positivity. Technical Report, Computer Science Department, The University of Chicago (January 2011). Available at:
20. Sam, S.: Symmetric quivers, invariant theory, and saturation theorems for the classical groups. (September, 2010)
21. Sturmfels, B.: On vector partition functions. J. Comb. Theory Ser. A 72(2) (1995)
22. Tardos, É.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250-256 (1986)
23. Valiant, L.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189-201 (1979)
24. Zelevinsky, A.: Littlewood-Richardson semigroups, new perspectives in geometric combinatorics.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition