On the hardness of computing the permanent of random matrices (extended abstract)
Uriel Feige, Carsten Lund · 1992
We study the complexity of computing the permanent on random inputs. We consider matrices drawn randomly from the space of n by n matrices with integer values between 0 and p–1, for any large enough prime p. We show that any polynomial time algorithm which computes the permanent correctly on even an exponentially small fraction of these matrices, implies the collapse of the polynomial-time hierarchy to its second level.