On the hardness of computing the permanent of random matrices
From MaRDI portal
Determinants, permanents, traces, other special matrix functions (15A15) Random matrices (algebraic aspects) (15B52) Numerical computation of determinants (65F40) Complexity and performance of numerical algorithms (65Y20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)
Recommendations
Cites work
- A note on enumerative counting
- Algebraic methods for interactive proof systems
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Highly resilient correctors for polynomials
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- NP is as easy as detecting unique solutions
- Some connections between bounded query classes and non-uniform complexity.
- The complexity of computing the permanent
- The Knowledge Complexity of Interactive Proof Systems
Cited in
(17)- A note on the permanent value problem
- Decoding of Reed Solomon codes beyond the error-correction bound
- On the hardness of approximating the permanent of structured matrices
- Limit theorems for random permanents with exchangeable structure
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Testing permanent oracles -- revisited
- Some upper bounds for permanents of (0, 1)-matrices
- scientific article; zbMATH DE number 1304313 (Why is no real title available?)
- scientific article; zbMATH DE number 7250159 (Why is no real title available?)
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Pseudorandom generators without the XOR lemma
- (Nondeterministic) hardness vs. non-malleability
- Hardness self-amplification: simplified, optimized, and unified
- Uniform black-box separations via non-malleable extractors
- Communication complexity vs randomness complexity in interactive proofs
- Permanental rank vs determinantal rank of random matrices over finite fields
- Masking traveling beams: optical solutions for NP-complete problems, trading space for time
This page was built for publication: On the hardness of computing the permanent of random matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1355377)
