Partition problems for geometric complexity theory, and the permanent vs. determinant problem.

Aram Bingham

arambingham@mines.edu

Geometric complexity theory (GCT) is a broad program spanning several areas of mathematics and computer science that seeks to address the most important question in computational complexity theory. It is widely held that some computational problems can only be solved by undertaking a costly search process, and the presumed difficulty of these problems (including integer factorization) is the foundation of modern cryptography and information security. However, despite efforts by many researchers over the past fifty years, no one has been able to prove that undiscovered, efficient algorithms for these difficult problems do not exist. GCT has arisen over the last 20 years as an attempt to apply the tools of algebraic geometry, representation theory, and combinatorics to approach a negative answer to what is known as the “P vs. NP problem.” Part of the GCT program requires that we have a firm understanding of certain constants called “Kronecker coefficients.” These are non-negative integers that are classical in an area of math called combinatorial representation theory, but there are practical formulas for computing coefficients only in very limited cases. Nevertheless, they are believed to have a particular combinatorial interpretation, meaning that their values describe the sizes of certain sets of explicitly describable objects. For a large class of Kronecker coefficients which are directly applicable to the broader goals of GCT, a so-called cancellative formula exists (meaning the Kronecker coefficient is obtained as the subtraction of two positive quantities), but this formula is of limited use for describing the (approximate) behavior of Kronecker coefficients. This information is necessary for GCT, because the numerical behavior of Kronecker coefficients can serve as a “certificate of hardness” for certain algorithmic problems like evaluating matrix permanents. Based on ideas that have proved successful in the simple cases, in this project we will work on eliminating the cancellation in the Kronecker coefficients formula, working towards a formula which is entirely positive. The cancellation in the formula that we begin from is between two families of objects that are very concrete – namely paths in a rectangular box that begin at one corner and end at the opposite corner, and can only take specified steps that are “up” and “over.” Thus, despite the sophisticated theory that gives context to this problem, the actual business of obtaining a positive formula for our Kronecker coefficients involves just finding a way to identify one set of visualizable objects with a subset of another. We will be able to experiment with rules to make this identification using computer algebra tools such as Python/SageMath. Once we identify candidate rules for eliminating the cancellation in the starting formula, we can set to proving that our mappings are well-defined and provide new positive formulas Kronecker coefficients. As a parallel line of investigation, it will also be valuable to better understand what is known as the “determinantal complexity” of the matrix permanent. The matrix permanent is a polynomial based on the entries of a square matrix, and it is believed that the computational complexity of evaluating permanents is exponential. However, the determinantal complexity is not fully understood even for small order permanents. For instance, this complexity measure for permanents of order 4 is known to be at least 8 and most 15, but is not known precisely. Furthermore, it is not known how many determinants are needed in order to write the permanent polynomial as a sum of determinants. This is a new line of inquiry which could possibly still have complexity theoretic consequences. This work will be of interest to the algebraic combinatorics, number theory, and theoretical computer science research fields. GCT has seen contributions by hundreds of researchers from diverse fields since its inception, and the aspects treated in this project involve concrete objects that are well-suited to an undergraduate research project.

Grand Challenge: Secure cyberspace.

Garey, M.R. and Johnson, D.S., 1979. Computers and intractability: A Guide to the Theory of NP-completeness. Grenet, B., 2011. “An upper bound for the permanent versus determinant problem.” Theory of Computing. Hahn, H., Huh, J., Lim, E. and Sohn, J., 2018. “From partition identities to a combinatorial approach to explicit Satake inversion.” Annals of Combinatorics, 22(3), pp.543-562. Pak, I. and Panova, G., 2014. “Unimodality via Kronecker products.” Journal of Algebraic Combinatorics, 40(4), pp.1103-1120. Mignon, Thierry, and Nicolas Ressayre. "A quadratic bound for the determinant and permanent problem." International Mathematics Research Notices 2004.79 (2004): 4241-4253. Pak, I. and Panova, G., 2013. “Strict unimodality of q-binomial coefficients.” Comptes Rendus Mathematique, 351(11-12), pp.415-418. Stanley, R.P., 2011. Enumerative Combinatorics Volume 1 (2nd edition). Cambridge studies in advanced mathematics.

<p class="Standard">Aram Bingham, <a href="mailto:arambingham@mines.edu"><span style="color: windowtext;text-decoration: none">arambingham@mines.edu</span></a></p>