Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality
Die Arbeit zeigt, dass die Nullstellen des Permanenz-Polynoms einer Zufallsmatrix mit komplexen Gaußschen Einträgen typischerweise in einem Radius von liegen, was effiziente Approximationsalgorithmen für Permanente bei polynomial kleinen Mittelwerten ermöglicht, gleichzeitig aber durch das Vorkommen von Nullstellen mit Betrag die durchschnittliche Härte der Approximation nicht widerlegt.