On the hardness of computing the permanent of random matrices

DOI10.1007/BF01262928zbMath0956.65037MaRDI QIDQ1355377

Uriel Feige, Carstent Lund

Publication date: 15 March 2001

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

computational complexity; random matrices; polynomial time algorithm; permanent; interactive proof systems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

15A15: Determinants, permanents, traces, other special matrix functions

65F40: Numerical computation of determinants

15B52: Random matrices (algebraic aspects)

65Y20: Complexity and performance of numerical algorithms

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Pseudorandom generators without the XOR lemma, Decoding of Reed Solomon codes beyond the error-correction bound, Limit theorems for random permanents with exchangeable structure, Some upper bounds for permanents of (0, 1)-matrices

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• A note on enumerative counting
• NP is as easy as detecting unique solutions
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Highly resilient correctors for polynomials
• Some connections between bounded query classes and non-uniform complexity.
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• The Knowledge Complexity of Interactive Proof Systems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Algebraic methods for interactive proof systems