Проблема Полиа для перманента

Two important functions in matrix theory, determinant and permanent, look very similar: $\det A = \sum_{\sigma \in S_{n}} (-1)^\sigma a_{1_{\sigma(1)}} \ldots a_{n_{\sigma(n)}}$ and $\mathrm{per} A = \sum_{\sigma \in S_{n}} a_{1_{\sigma(1)}} \ldots a_{n_{\sigma(n)}}$, here $A = (a_{ij}) \in M_{n} (\mathbb F)$ is an $n \times n$ matrix over a field $\mathbb F$ and $S_{n}$ denotes the set of all permutations of the set {1, . . . , n}. While the computation of the determinant can be done in a polynomial time, it is still an open question, if there are such algorithms to compute the permanent. Due to this reason, starting from the work by Polya, 1913, different approaches to convert the permanent into the determinant were under the intensive investigation. We plan to give a short exposition of this theory during the past century including our recent research results. In particular, we prove that there are no bijective converters between permanent and determinant over finite fields. We also plan to provide sharp upper bounds for permanents of (1,-1)-matrices depending on their rank, which proves the Krauter conjecture (1985) answering the question by Wang (1974).
The talk is based on a series of joint works with Mikhail Budrevich, Gregor Dolinar, Bojan Kuzma and Marko Orel.