On the public citation graph

On the hardness of computing the permanent of random matrices

https://doi.org/10.1007/bf01262928
0 signed · 64 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-09519-5_72openalex-snapshot
Probabilistic algorithms for verification of polynomial identities
inferredcites →https://doi.org/10.1007/3-540-52282-4_30openalex-snapshot
Hiding instances in multioracle queries
inferredcites →https://doi.org/10.1016/0020-0190(87)90232-8openalex-snapshot
Does co-NP have short interactive proofs?
inferredcites →https://doi.org/10.1016/0020-0190(91)90103-oopenalex-snapshot
A note on enumerative counting
inferredcites →https://doi.org/10.1016/0020-0190(92)90195-2openalex-snapshot
Highly resilient correctors for polynomials
inferredcites →https://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot
The Complexity of Computing the Permanent
inferredcites →https://doi.org/10.1016/0304-3975(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/s0890-5401(03)00091-9openalex-snapshot
Some connections between bounded query classes and non-uniform complexity
inferredcites →https://doi.org/10.1016/s0924-6509(08)x7030-8openalex-snapshot
The Theory of Error-Correcting Codes
inferredcites →https://doi.org/10.1090/dimacs/002/13openalex-snapshot
New directions in testing
inferredcites →https://doi.org/10.1109/sfcs.1984.715947openalex-snapshot
RSA/Rabin Bits are 1/2 + 1 / Poly (Log N) Secure
inferredcites →https://doi.org/10.1109/sfcs.1989.63527openalex-snapshot
On the computational power of PP and (+)P
inferredcites →https://doi.org/10.1137/0213053openalex-snapshot
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
inferredcites →https://doi.org/10.1137/0218012openalex-snapshot
The Knowledge Complexity of Interactive Proof Systems
inferredcites →https://doi.org/10.1142/s0129054191000066openalex-snapshot
#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
inferredcites →https://doi.org/10.1145/100216.100271openalex-snapshot
The discrete log is very discreet
inferredcites →https://doi.org/10.1145/103418.103429openalex-snapshot
Self-testing/correcting for polynomials and for approximate functions
inferredcites →https://doi.org/10.1145/12130.12137openalex-snapshot
Private coins versus public coins in interactive proof systems
inferredcites →https://doi.org/10.1145/146585.146605openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1145/322217.322225openalex-snapshot
Fast Probabilistic Algorithms for Verification of Polynomial Identities
inferredcites →https://doi.org/10.1145/800061.808740openalex-snapshot
The complexity of approximate counting
inferredcites →https://doi.org/10.5948/upo9781614440147openalex-snapshot
Combinatorial Mathematics

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jcom.1997.0439openalex-snapshot
Decoding of Reed Solomon Codes beyond the Error-Correction Bound
inferred← citeshttps://doi.org/10.1006/jcss.2000.1730openalex-snapshot
Pseudorandom Generators without the XOR Lemma
inferred← citeshttps://doi.org/10.1007/10722028_1openalex-snapshot
The Complexity of Some Lattice Problems
inferred← citeshttps://doi.org/10.1007/3-540-45537-x_10openalex-snapshot
Polynomial Reconstruction Based Cryptography
inferred← citeshttps://doi.org/10.1007/978-3-030-17653-2_17openalex-snapshot
Non-Malleable Codes Against Bounded Polynomial Time Tampering
inferred← citeshttps://doi.org/10.1007/978-3-031-15802-5_6openalex-snapshot
(Nondeterministic) Hardness vs. Non-malleability
inferred← citeshttps://doi.org/10.1007/978-3-032-01855-7_19openalex-snapshot
Uniform Black-Box Separations via Non-malleable Extractors
inferred← citeshttps://doi.org/10.1007/978-3-0348-9078-6_135openalex-snapshot
The Computational Complexity of Counting
inferred← citeshttps://doi.org/10.1007/978-3-540-48413-4_13openalex-snapshot
Probabilistic and Deterministic Approximations of the Permanent
inferred← citeshttps://doi.org/10.1007/978-88-470-2107-5_22openalex-snapshot
On the permanent of certain circulant matrices
inferred← citeshttps://doi.org/10.1007/b104335openalex-snapshot
List Decoding of Error-Correcting Codes
inferred← citeshttps://doi.org/10.1007/s00037-002-0174-3openalex-snapshot
On the hardness of approximating the permanent of structured matrices
inferred← citeshttps://doi.org/10.1007/s00037-007-0232-yopenalex-snapshot
Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword
inferred← citeshttps://doi.org/10.1007/s00037-016-0128-9openalex-snapshot
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions
inferred← citeshttps://doi.org/10.1007/s00224-007-9071-0openalex-snapshot
Relations between Average-Case and Worst-Case Complexity
inferred← citeshttps://doi.org/10.1007/s004930070007openalex-snapshot
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90195-2openalex-snapshot
Highly resilient correctors for polynomials
inferred← citeshttps://doi.org/10.1016/j.jmva.2004.01.003openalex-snapshot
Limit theorems for random permanents with exchangeable structure
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.06.030openalex-snapshot
Masking traveling beams: Optical solutions for NP-complete problems, trading space for time
inferred← citeshttps://doi.org/10.1016/s0024-3795(96)00644-1openalex-snapshot
On the Permanent of Certain (0, 1) Toeplitz Matrices
inferred← citeshttps://doi.org/10.1016/s0024-3795(99)00012-9openalex-snapshot
How fast can one compute the permanent of circulant matrices?
inferred← citeshttps://doi.org/10.1080/09720502.2007.10700483openalex-snapshot
Some upper bounds for permanents of (0, 1)-matrices
inferred← citeshttps://doi.org/10.1109/ccc.1999.766274openalex-snapshot
Some recent progress on the complexity of lattice problems
inferred← citeshttps://doi.org/10.1109/ccc.2005.16openalex-snapshot
On Constructing Parallel Pseudorandom Generators from One-Way Functions
inferred← citeshttps://doi.org/10.1109/focs.2013.84openalex-snapshot
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
inferred← citeshttps://doi.org/10.1109/focs.2019.00078openalex-snapshot
The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
inferred← citeshttps://doi.org/10.1109/isit44484.2020.9174373openalex-snapshot
Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average
inferred← citeshttps://doi.org/10.1109/sfcs.1996.548475openalex-snapshot
Maximum likelihood decoding of Reed Solomon codes
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892063openalex-snapshot
Extracting randomness from samplable distributions
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959879openalex-snapshot
Coding theory: Tutorial & survey
inferred← citeshttps://doi.org/10.1137/080735096openalex-snapshot
Hardness Amplification Proofs Require Majority
inferred← citeshttps://doi.org/10.1137/s0097539705447281openalex-snapshot
Using Nondeterminism to Amplify Hardness
inferred← citeshttps://doi.org/10.1145/1007352.1007389openalex-snapshot
Using nondeterminism to amplify hardness
inferred← citeshttps://doi.org/10.1145/1620491.1620505openalex-snapshot
SIGACT news complexity theory column 64
inferred← citeshttps://doi.org/10.1145/276698.276880openalex-snapshot
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
inferred← citeshttps://doi.org/10.1145/301250.301397openalex-snapshot
Pseudorandom generators without the XOR Lemma (extended abstract)
inferred← citeshttps://doi.org/10.1145/3618260.3649735openalex-snapshot
Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions
inferred← citeshttps://doi.org/10.1145/504192.504194openalex-snapshot
SIGACT News complexity theory column 32
inferred← citeshttps://doi.org/10.1145/568425.568432openalex-snapshot
SIGACT news complexity theory column 34
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.9openalex-snapshot
Pseudorandomness When the Odds are Against You
inferred← citeshttps://doi.org/10.48550/arxiv.1003.3967openalex-snapshot
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.