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 complexityrandom matricespolynomial time algorithmpermanentinteractive proof systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40) Random matrices (algebraic aspects) (15B52) Complexity and performance of numerical algorithms (65Y20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Limit theorems for random permanents with exchangeable structure ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Masking traveling beams: optical solutions for NP-complete problems, trading space for time ⋮ Decoding of Reed Solomon codes beyond the error-correction bound ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Some upper bounds for permanents of (0, 1)-matrices ⋮ Pseudorandom generators without the XOR lemma

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

This page was built for publication: On the hardness of computing the permanent of random matrices