On the hardness of computing the permanent of random matrices
type: Item
instance of: scholarly article
title: On the hardness of computing the permanent of random matrices
zbMATH Open document ID: 0956.65037
DOI: 10.1007/BF01262928
author: C. Lund
author: Uriel Feige
published in: Computational Complexity
publication date: 2001-03-15T00:00:00Z
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15B52
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 1013423
zbMATH Keywords: random matrices
zbMATH Keywords: computational complexity
zbMATH Keywords: interactive proof systems
zbMATH Keywords: permanent
zbMATH Keywords: polynomial time algorithm
MaRDI profile type: Publication
cites work: Some connections between bounded query classes and non-uniform complexity.
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: Does co-NP have short interactive proofs ?
cites work: A note on enumerative counting
cites work: Highly resilient correctors for polynomials
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Algebraic methods for interactive proof systems
cites work: Q4146667
cites work: Q3851094
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: The complexity of computing the permanent
cites work: NP is as easy as detecting unique solutions
description: scientific article; zbMATH DE number 1013423