On the public citation graph

Polynomial-time compression

https://doi.org/10.1007/bf01276437
0 signed · 45 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-52921-7_71openalex-snapshot
Algorithms from complexity theory: Polynomial-time operations for complex sets
inferredcites →https://doi.org/10.1007/bf02090763openalex-snapshot
The complexity of ranking simple languages
inferredcites →https://doi.org/10.1007/bf02125350openalex-snapshot
Query complexity, or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?
inferredcites →https://doi.org/10.1016/0020-0190(76)90097-1openalex-snapshot
Relative complexity of checking and evaluating
inferredcites →https://doi.org/10.1016/0020-0190(88)90096-8openalex-snapshot
An ordered minimal perfect hashing scheme with single parameter
inferredcites →https://doi.org/10.1016/0022-0000(83)90027-2openalex-snapshot
A low and a high hierarchy within NP
inferredcites →https://doi.org/10.1016/0022-0000(84)90068-0openalex-snapshot
The complexity of facets (and some facets of complexity)
inferredcites →https://doi.org/10.1016/0022-0000(89)90025-1openalex-snapshot
The strong exponential hierarchy collapses
inferredcites →https://doi.org/10.1016/0022-0000(90)90038-mopenalex-snapshot
On the complexity of ranking
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(81)90061-xopenalex-snapshot
Bounded query machines: On NP and PSPACE
inferredcites →https://doi.org/10.1016/0304-3975(81)90062-1openalex-snapshot
Bounded query machines: On NP() and NPQUERY()
inferredcites →https://doi.org/10.1016/0304-3975(83)90003-8openalex-snapshot
Oracle-dependent properties of the lattice of NP sets
inferredcites →https://doi.org/10.1016/0304-3975(84)90111-7openalex-snapshot
Computation times of NP sets of different densities
inferredcites →https://doi.org/10.1016/0304-3975(85)90139-2openalex-snapshot
Reductions among polynomial isomorphism types
inferredcites →https://doi.org/10.1016/0304-3975(85)90140-9openalex-snapshot
Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
inferredcites →https://doi.org/10.1016/0304-3975(91)90388-iopenalex-snapshot
On sets polynomially enumerable by iteration
inferredcites →https://doi.org/10.1016/s0019-9958(85)80004-8openalex-snapshot
Sparse sets in NP-P: EXPTIME versus NEXPTIME
inferredcites →https://doi.org/10.1109/sct.1992.215396openalex-snapshot
How hard are sparse sets?
inferredcites →https://doi.org/10.1109/sfcs.1986.50openalex-snapshot
Storing a dynamic sparse table
inferredcites →https://doi.org/10.1109/sfcs.1988.21968openalex-snapshot
Dynamic Perfect Hashing: Upper and Lower Bounds
inferredcites →https://doi.org/10.1109/swat.1972.29openalex-snapshot
The equivalence problem for regular expressions with squaring requires exponential space
inferredcites →https://doi.org/10.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0217018openalex-snapshot
Complexity Measures for Public-Key Cryptosystems
inferredcites →https://doi.org/10.1137/0217075openalex-snapshot
P-Printable Sets
inferredcites →https://doi.org/10.1145/22145.22194openalex-snapshot
Compression and ranking
inferredcites →https://doi.org/10.1145/358027.358051openalex-snapshot
The study of an ordered minimal perfect hashing scheme
inferredcites →https://doi.org/10.1145/359863.359887openalex-snapshot
Perfect hashing functions

What points at this work

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

inferred← citeshttps://doi.org/10.1002/malq.19990450104openalex-snapshot
Towards the Actual Relationship Between NP and Exponential Time
inferred← citeshttps://doi.org/10.1007/3-540-62592-5_78openalex-snapshot
On sets with easy certificates and the existence of one-way permutations
inferred← citeshttps://doi.org/10.1007/978-3-030-13435-8_13openalex-snapshot
Closure and Nonclosure Properties of the Compressible and Rankable Sets
inferred← citeshttps://doi.org/10.1007/978-3-642-13962-8_1openalex-snapshot
Avoiding Simplicity Is Complex
inferred← citeshttps://doi.org/10.1007/bfb0023452openalex-snapshot
Resource-bounded kolmogorov complexity revisited
inferred← citeshttps://doi.org/10.1007/s00224-011-9334-7openalex-snapshot
Avoiding Simplicity is Complex
inferred← citeshttps://doi.org/10.1007/s00224-023-10118-yopenalex-snapshot
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00204-9openalex-snapshot
Scalability and the isomorphism problem
inferred← citeshttps://doi.org/10.1016/j.jcss.2018.10.003openalex-snapshot
Recursion-theoretic ranking and compression
inferred← citeshttps://doi.org/10.1016/j.jcss.2021.02.004openalex-snapshot
Closure and nonclosure properties of the classes of compressible and rankable sets
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00014-1openalex-snapshot
Characterizing the existence of one-way permutations
inferred← citeshttps://doi.org/10.1137/s009753979834388xopenalex-snapshot
Resource-Bounded Kolmogorov Complexity Revisited
inferred← citeshttps://doi.org/10.3217/jucs-005-12-0828openalex-snapshot
On the Power of Positive Turing Reductions
inferred← citeshttps://doi.org/10.48550/arxiv.1611.01696openalex-snapshot
Closure and Nonclosure Properties of the Compressible and Rankable Sets
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9907040openalex-snapshot
Characterizations of the Existence of Partial and Total One-Way Permutations
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.