The partition algebra: a new approach to the symmetric group and applications to P vs NP.

The Kronecker problem is a classical problem in Mathematics, which has been open for over a hundred years. It asks for a description of some coefficients, called the Kronecker coefficients, appearing in the representation theory of the symmetric group. More recently, this problem has been shown to play a key role in Geometric Complexity theory, an approach that seeks to settle the famous P vs NP problem.

We have recently proposed a completely new approach to the Kronecker problem using the duality between the symmetric group and the partition algebra. Early results suggest that this may well lead to a complete solution. This proposal aims at developing this tool further (and extending it to positive characteristics) to give a systematic study of the ordinary and modular representation theory of the symmetric group.

In parallel, we plan to liaise with the Computer Science community to investigate the implications of our work to the celebrated P vs NP problem.

The central idea in this project is to use an algebraic structure coming from Mathematical Physics, to tackle the classical Kronecker problem in Pure Mathematics.

The main impact, outside of the academic community, comes from the deep connections between the Kronecker problem and the famous P vs NP problem. The P vs NP problem is one of the 7 Millenium prize problems set up be the Clay Mathematical Institute in Cambridge Massachussets
in 2000 and considered to be the most important open problems in
Mathematics (only one of them has been solved to date).
It is the central question in an area of theoretical computer
science called Computational Complexity, which focusses on quantifying the efficiency
of algorithms to solve computational problems. It is well-known that a solution to the P vs NP problem would have enormous impact on our society, from cryptography to many aspects of logistics.