On the public citation graph
Three ? P 2 -complete problems in computational learning theory
0 signed · 46 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/bf00289117openalex-snapshot
The complexity of combinatorial problems with succinct input representation
inferredcites →https://doi.org/10.1016/0022-0000(80)90041-0openalex-snapshot
Finding patterns common to a set of strings
inferredcites →https://doi.org/10.1016/0022-0000(87)90006-7openalex-snapshot
A note on the two-variable pattern-finding problem
inferredcites →https://doi.org/10.1016/0022-0000(90)90028-jopenalex-snapshot
Prediction-preserving reducibility
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(76)90062-1openalex-snapshot
Complete sets and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(84)90092-6openalex-snapshot
Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is ΣP2-complete
inferredcites →https://doi.org/10.1016/b978-1-55860-141-3.50049-3openalex-snapshot
Learning String Patterns and Tree Patterns from Examples
inferredcites →https://doi.org/10.1023/a:1022648800760openalex-snapshot
The Strength of Weak Learnability
inferredcites →https://doi.org/10.1109/sfcs.1982.65openalex-snapshot
Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is S2p-complete
inferredcites →https://doi.org/10.1109/sfcs.1988.21928openalex-snapshot
Predicting (0, 1)-functions on randomly drawn points
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.1145/100216.100223openalex-snapshot
On the necessity of Occam algorithms
inferredcites →https://doi.org/10.1145/322217.322221openalex-snapshot
Equivalences Among Relational Expressions with the Union and Difference Operators
inferredcites →https://doi.org/10.1145/48014.63140openalex-snapshot
Computational limitations on learning from examples
inferredcites →https://doi.org/10.1145/76359.76371openalex-snapshot
Learnability and the Vapnik-Chervonenkis dimension
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.5555/92571.92613openalex-snapshot
Pattern languages are not learnable
inferredcites →https://doi.org/10.5555/93025.93040openalex-snapshot
Equivalence of models for polynomial learnability
inferredcites →https://doi.org/10.5555/93335.93343openalex-snapshot
A polynomial-time algorithm for learning k-variable pattern languages from examples
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcss.2000.1729openalex-snapshot
Graph Ramsey Theory and the Polynomial Hierarchy
inferred← citeshttps://doi.org/10.1007/3-540-44418-1_12openalex-snapshot
A Practical Algorithm to Find the Best Subsequence Patterns
inferred← citeshttps://doi.org/10.1007/3-540-46769-6_29openalex-snapshot
On Learning Unions of Pattern Languages and Tree Patterns
inferred← citeshttps://doi.org/10.1007/978-1-4613-3557-3_15openalex-snapshot
On the Complexity of Min-Max Optimization Problems and their Approximation
inferred← citeshttps://doi.org/10.1007/978-3-030-41672-0_1openalex-snapshot
In Memoriam: Ker-I Ko (1950–2018)
inferred← citeshttps://doi.org/10.1007/bf03037530openalex-snapshot
Polynomial-time learning of elementary formal systems
inferred← citeshttps://doi.org/10.1007/pl00001593openalex-snapshot
Complexity theoretic hardness results for query learning
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.04.035openalex-snapshot
Revisiting Shinohara's algorithm for computing descriptive patterns
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00402-9openalex-snapshot
On learning unions of pattern languages and tree patterns in the mistake bound model
inferred← citeshttps://doi.org/10.1109/icde55515.2023.00154openalex-snapshot
Fair Group Summarization with Graph Patterns
inferred← citeshttps://doi.org/10.1109/sct.1995.514862openalex-snapshot
Optimizing TRIEs for ordered pattern matching is Π/sub 2//sup P/-complete
inferred← citeshttps://doi.org/10.1145/301250.301411openalex-snapshot
Graph Ramsey theory and the polynomial hierarchy
inferred← citeshttps://doi.org/10.1145/3762196openalex-snapshot
The Complexity of Homomorphism Reconstructibility
inferred← citeshttps://doi.org/10.1145/582475.582484openalex-snapshot
SIGACT news complexity theory comun 37
inferred← citeshttps://doi.org/10.1145/601819.601829openalex-snapshot
SIGACT news complexity theory column 38
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0102019openalex-snapshot
Easy and Hard Constraint Ranking in OT: Algorithms and Complexity
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.