ON THE HARDNESS OF COMPUTING THE PERMANENT OF RANDOM MATRICES

Extending a line of research initiated by Lipton, we study the complex ity of computing the permanent of random n by n matrices with integer values between 0 and p - I, for any suitably large prime p. Previous t o our work, it was shown hard to compute the permanent of half these m atrices (by Gemmell and Sudan), and to enumerate for any matrix a poly nomial number of options for its permanent (by Cai and Hemachandra, an d by Toda). We show that unless the polynomial-time hierarchy collapse s to its second level, no polynomial time algorithm can compute the pe rmanent of every matrix with probability at least 13n(3)/p, nor can it compute the permanent of at least a (49n(3)/root p)-fraction of the m atrices. As p may be exponential in n, these represent very low succes s probabilities for any efficient algorithm that attempts to compute t he permanent. For 0/1 matrices, our results show that their permanents cannot be guessed with probability greater than 1/2(n1-epsilon). We a lso show that it is hard to get even partial information about the val ue of the permanent module p. For random matrices we show that any bal anced polynomial-time 0/1 predicate (e.g., the least significant bit, the parity of all the bits, the quadratic residuosity character) canno t be guessed with probability significantly greater than 1/2 (unless t he polynomial-time hierarchy collapses). This result extends to showin g simultaneous hardness for linear size groups of bits.