On the public citation graph

Rankable distributions do not provide harder instances than uniform distributions

https://doi.org/10.1007/bfb0030860
0 signed · 32 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.1006/jcss.1995.1014openalex-snapshot
On the NP-Isomorphism Problem with Respect to Random Instances
inferredcites →https://doi.org/10.1007/3-540-56287-7_100openalex-snapshot
Structural average case complexity
inferredcites →https://doi.org/10.1007/3-540-56503-5_64openalex-snapshot
Precise average case complexity
inferredcites →https://doi.org/10.1016/0001-8708(77)90052-4openalex-snapshot
Distributions in statistics: Discrete distributions
inferredcites →https://doi.org/10.1016/0020-0190(92)90138-lopenalex-snapshot
Average case complexity under the universal distribution equals worst-case complexity
inferredcites →https://doi.org/10.1016/0020-0190(94)90048-5openalex-snapshot
On average time hierarchies
inferredcites →https://doi.org/10.1016/0022-0000(91)90007-ropenalex-snapshot
Average case completeness
inferredcites →https://doi.org/10.1016/0022-0000(92)90019-fopenalex-snapshot
On the theory of average case complexity
inferredcites →https://doi.org/10.1016/0196-6774(84)90032-4openalex-snapshot
The NP-completeness column: An ongoing guide
inferredcites →https://doi.org/10.1016/0196-6774(86)90020-9openalex-snapshot
The NP-completeness column: An ongoing guide
inferredcites →https://doi.org/10.1090/s0002-9947-1965-0170805-7openalex-snapshot
On the Computational Complexity of Algorithms
inferredcites →https://doi.org/10.1109/fscs.1990.89604openalex-snapshot
No better ways to generate hard NP instances than picking uniformly at random
inferredcites →https://doi.org/10.1112/plms/s2-10.1.54openalex-snapshot
Properties of Logarithmico-Exponential Functions
inferredcites →https://doi.org/10.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0215020openalex-snapshot
Average Case Complete Problems
inferredcites →https://doi.org/10.1137/0216034openalex-snapshot
Expected Computation Time for Hamiltonian Path problem
inferredcites →https://doi.org/10.1137/0222059openalex-snapshot
Randomizing Reductions of Search Problems
inferredcites →https://doi.org/10.1137/s0097539792232070openalex-snapshot
Matrix Transformation Is Complete for the Average Case
inferredcites →https://doi.org/10.1145/129712.129774openalex-snapshot
Average case intractability of matrix and diophantine problems (extended abstract)
inferredcites →https://doi.org/10.1145/225058.225153openalex-snapshot
Average-case completeness of a word problem for groups
inferredcites →https://doi.org/10.1145/62212.62231openalex-snapshot
Random instances of a graph coloring problem are hard
inferredcites →https://doi.org/10.2307/1402186openalex-snapshot
Distribution in Statistics: Discrete Distributions

What points at this work

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

inferred← citeshttps://doi.org/10.1007/3-540-60922-9_28openalex-snapshot
Fine separation of average time complexity classes
inferred← citeshttps://doi.org/10.1007/3-540-61332-3_164openalex-snapshot
Reductions and convergence rates of average time
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_12openalex-snapshot
Average-Case Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-1-4613-3394-4_15openalex-snapshot
Average-Case Intractable NP Problems
inferred← citeshttps://doi.org/10.1007/978-3-540-46588-1_26openalex-snapshot
Making Hash Functions from Block Ciphers Secure and Efficient by Using Convolutional Codes
inferred← citeshttps://doi.org/10.1007/pl00009267openalex-snapshot
Reductions Do Not Preserve Fast Convergence Rates in Average Time
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00272-1openalex-snapshot
No NP problems averaging over ranking of distributions are harder
inferred← citeshttps://doi.org/10.1137/s0097539796311715openalex-snapshot
Fine Separation of Average-Time Complexity Classes
inferred← citeshttps://doi.org/10.1145/225058.225153openalex-snapshot
Average-case completeness of a word problem for groups
inferred← citeshttps://doi.org/10.1145/230514.571643openalex-snapshot
Technical Report Column
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.