On the public citation graph

Resource-bounded kolmogorov complexity revisited

https://doi.org/10.1007/bfb0023452
0 signed · 40 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-60922-9_7openalex-snapshot
The complexity of generating and checking proofs of membership
inferredcites →https://doi.org/10.1007/978-1-4757-3860-5openalex-snapshot
An Introduction to Kolmogorov Complexity and Its Applications
inferredcites →https://doi.org/10.1007/978-3-030-11298-1openalex-snapshot
An Introduction to Kolmogorov Complexity and Its Applications
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/bf01202283openalex-snapshot
Structural analysis of the complexity of inverse functions
inferredcites →https://doi.org/10.1007/bf01276437openalex-snapshot
Polynomial-time compression
inferredcites →https://doi.org/10.1007/bf02090764openalex-snapshot
Classes of bounded nondeterminism
inferredcites →https://doi.org/10.1016/0020-0190(96)00030-0openalex-snapshot
Functions computable with limited access to NP
inferredcites →https://doi.org/10.1016/0022-0000(88)90039-6openalex-snapshot
The complexity of optimization problems
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/0304-3975(94)00080-3openalex-snapshot
Computing functions with parallel queries to NP
inferredcites →https://doi.org/10.1016/0304-3975(95)00097-6openalex-snapshot
On resource-bounded instance complexity
inferredcites →https://doi.org/10.1016/s0019-9958(84)80056-xopenalex-snapshot
The complexity of promise problems with applications to public-key cryptography
inferredcites →https://doi.org/10.1109/ccc.1996.507686openalex-snapshot
The complexity of knowledge representation
inferredcites →https://doi.org/10.1109/sct.1994.315819openalex-snapshot
On functions computable with nonadaptive queries to NP
inferredcites →https://doi.org/10.1109/sfcs.1989.63482openalex-snapshot
Decision versus search problems in super-polynomial time
inferredcites →https://doi.org/10.1137/s0097539794268315openalex-snapshot
Computing Solutions Uniquely Collapses the Polynomial Hierarchy
inferredcites →https://doi.org/10.1145/800061.808762openalex-snapshot
A complexity theoretic approach to randomness
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures

What points at this work

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

inferred← citeshttps://doi.org/10.1006/inco.2001.3056openalex-snapshot
Sparse Sets and Collapse of Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-45294-x_1openalex-snapshot
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_26openalex-snapshot
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies
inferred← citeshttps://doi.org/10.1007/978-3-319-06089-7_5openalex-snapshot
Finite State Incompressible Infinite Sequences
inferred← citeshttps://doi.org/10.1007/bf02950407openalex-snapshot
Some structural properties of SAT
inferred← citeshttps://doi.org/10.1007/bfb0028551openalex-snapshot
Nearly optimal language compression using extractors
inferred← citeshttps://doi.org/10.1007/s00037-005-0199-5openalex-snapshot
Language compression and pseudorandom generators
inferred← citeshttps://doi.org/10.1016/j.ic.2015.11.003openalex-snapshot
Finite state incompressible infinite sequences
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.11.033openalex-snapshot
Computational depth: Concept and applications
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.06.021openalex-snapshot
Finite state complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.03.007openalex-snapshot
A linearly computable measure of string complexity
inferred← citeshttps://doi.org/10.1023/a:1025645221773openalex-snapshot
Algorithms for Sat and Upper Bounds on Their Complexity
inferred← citeshttps://doi.org/10.1109/ccc.1997.612295openalex-snapshot
Six hypotheses in search of a theorem
inferred← citeshttps://doi.org/10.1109/ccc.1998.694616openalex-snapshot
Randomness is hard
inferred← citeshttps://doi.org/10.1109/ccc.2000.856742openalex-snapshot
New bounds for the language compression problem
inferred← citeshttps://doi.org/10.1109/ccc.2001.933893openalex-snapshot
Computational depth
inferred← citeshttps://doi.org/10.1109/icee55646.2022.9827049openalex-snapshot
A Simulation of Bayesian Surprise
inferred← citeshttps://doi.org/10.1145/276698.276737openalex-snapshot
NP might not be as easy as detecting unique solutions
inferred← citeshttps://doi.org/10.1145/3665163openalex-snapshot
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory
inferred← citeshttps://doi.org/10.1504/ijidss.2008.021971openalex-snapshot
On the complexity of system designs
inferred← citeshttps://doi.org/10.4204/eptcs.31.6openalex-snapshot
Finite-State Complexity and the Size of Transducers
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.