On the hardness of computing the permanent of random matrices
Tóm tắt
Từ khóa
Tài liệu tham khảo
W. Alexi, B. Chor, O. Goldreich, and C. Schnorr, RSA/Rabin bits are 1/2+1/poly(logN) secure. InProceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, 449?457.
A. Amir, R. Beigel, and W. I. Gasarch, Some connections between bounded query classes and non-uniform complexity. InProceedings of the 5th Annual Conference on Structure in Complexity Theory, 1990, 232?243.
L. Babai andS. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes.Journal of Computer and System Sciences 36(2) (1988), 254?276.
D. Beaver and J. Feigenbaum, Hiding instances in multioracle queries. InProceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Sciencs, Lecture Notes in Computer Science415 (1990), 37?48.
E. Berlekamp and L. Welch, Error correction of algebraic block codes. US Patent Number 4,633, 470, 1991.
M. Blum andS. Micali, How to generate cryptographically strong sequences of pseudo-random bits.SIAM Journal on Computing 13(4) (1984), 850?864.
R. Boppana, J. Håstad, andS. Zachos, Does co-NP have short interactive proofs?Information Processing Letters 25(2) (1987), 127?132.
J. Cai andL. Hemachandra, A Note on Enumerative Counting.Information Processing Letters 38(4) (1991), 215?219.
P. Gemmell andM. Sudan, Highly resilient correctors for polynomials.Information Processing Letters 43, (1992), 169?174.
P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson, Selftesting/correcting for polynomials and for approximate functions. InProceedings of the Twenty-third Annual ACM Symposium on the Theory of Computing, 1991, 32?42.
S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems. InRandomness and Computation, ed.S. Micali, vol. 5 ofAdvances in Computing Research, JAI Press, 1989, 73?90.
S. Goldwasser, S. Micali, andC. Rackoff, The knowledge complexity of interactive proof-systems.SIAM Journal on Computing 18(1) (1989), 186?208.
R. Lipton, New directions in testing. InDistributed computing and Cryptography, ed.J. Feigenbaum and M. Merritt, vol. 2 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1991, 191?202.
C. Lund, L. Fortnow, H. Karloff, andN. Nisan, Algebraic methods for interactive proof systems.Journal of the ACM 39(4) (1992), 859?868.
F. MacWilliams and N. Sloane,The Theory of Error-Correcting Codes. North-Holland, 1981.
A. Schrift and A. Shamir, The discrete log is very discreet. InProceedings of the Twenty-second Annual ACM Symposium on the Theory of Computing, 1990, 405?415.
J. T. Schwartz, Probabilistic algorithms for verification of polynomial identities.Journal of the ACM 27 (1980), 701?717.
L. Stockmeyer, The complexity of approximate counting. InProceedings of the Twnty-first Annual ACM Symposium on the Theory of Computing, 1983, 118?126.
S. Toda, On the computational power of PP and ?P. InProceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, 514?519.
S. Toda, 1990. Personal communication in Cai & Hemachandra (1991).
L. Valiant, The complexity of computing the permanent.Theoretical Computer Science 8 (1979), 189?201.
L. Valiant andV. Vazirani, NP is as easy as detecting unique solutions.Theoretical Computer Science 47(1) (1986), 85?93.