Project Info

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

Aram Bingham

Project Goals and Description:

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.

More Information:

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.

Primary Contacts:

<p class="Standard">Aram Bingham, <a href=""><span style="color: windowtext;text-decoration: none"></span></a></p>

Student Preparation


Some experience programming (preferably in Python) will be necessary – proficiency at the sophomore coursework level or better is desired. Familiarity with logic, proofs, sets, counting and functions from e. g.  CSCI 358 (Discrete Mathematics) or MATH 300 (Foundations of Adv. Math.) will also be essential. Demonstrated ability to work independently and manage time well will also be necessary. Experience with mathematical writing using LaTeX is also beneficial, though not essential. Other technical skills or background content knowledge can be filled in as the project progresses.




Student will gain knowledge of common techniques in combinatorics research, including fluency with running computer experiments to test combinatorial ideas and familiarity with the SageMath computer algebra system. The student will also gain experience writing formal, research-article style proofs and greater familiarity with mathematical typesetting in LaTeX. Deep knowledge of algebro-combinatorial theory will not be a focus of the project, but the student will gain some literacy with the state of modern   research in combinatorics and complexity theory.


During semesters, we will have weekly meetings, allowing at least an hour to discuss progress, share ideas, and offer direction. I view undergraduate research projects as true collaborations, in which all participants work off each other’s strengths in order to make progress on a problem, so I work closely with students to determine which tasks and parts of the project are best suited to each one’s interests and abilities. I am also available outside of scheduled meeting times, either over e-mail or in additional office hours to help troubleshoot issues that come up in between meetings.

I model steps towards partial progress for students during meetings so that the time they spend working independently is well-used, with a clear understanding of what they should be attempting to do. In research, many attempts often end in failure, so I am sure to describe my own failed ideas and the insights they have sometimes brought.

I like to ensure that students have an opportunity to present their work in some extramural forum at the end of the project. I plan to support the student through this process, including offering coaching on abstract submission, poster/talk design, research conference etiquette etc. Should the opportunity arise where journal submission becomes a viable possibility, I would gladly offer guidance and help with this process as well.

My mentoring relationships often extend beyond the duration of direct contact, and I enjoy being available for students to consult as they progress through their careers. By understanding their goals and interests, I try to shape the research experience to something that they will find valuable for years to come.


Share This