On the public citation graph
Complexity theoretic hardness results for query learning
0 signed · 74 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.1006/inco.1995.1149openalex-snapshot
Read-Twice DNF Formulas Are Properly Learnable
inferredcites →https://doi.org/10.1006/jcss.1997.1533openalex-snapshot
An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution
inferredcites →https://doi.org/10.1007/bf00114777openalex-snapshot
Complexity Results on Learning by Neural Nets
inferredcites →https://doi.org/10.1007/bf00114802openalex-snapshot
Learning Conjunctive Concepts in Structural Domains
inferredcites →https://doi.org/10.1007/bf00116034openalex-snapshot
Negative Results for Equivalence Queries
inferredcites →https://doi.org/10.1007/bf00116035openalex-snapshot
Polynomial Time Learnability of Simple Deterministic Languages
inferredcites →https://doi.org/10.1007/bf00992675openalex-snapshot
Learning conjunctions of Horn clauses
inferredcites →https://doi.org/10.1007/bf00993976openalex-snapshot
Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts
inferredcites →https://doi.org/10.1007/bf01200064openalex-snapshot
Three ? P 2 -complete problems in computational learning theory
inferredcites →https://doi.org/10.1007/bf01205054openalex-snapshot
An algorithm to learn read-once threshold formulas, and transformations between learning models
inferredcites →https://doi.org/10.1016/0012-365x(93)90372-zopenalex-snapshot
Combinatorial characterization of read-once formulae
inferredcites →https://doi.org/10.1016/0022-0000(90)90028-jopenalex-snapshot
Prediction-preserving reducibility
inferredcites →https://doi.org/10.1016/0095-8956(77)90077-6openalex-snapshot
A note on the production of matroid minors
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(92)90367-oopenalex-snapshot
On the necessity of Occam algorithms
inferredcites →https://doi.org/10.1016/0890-5401(87)90052-6openalex-snapshot
Learning regular sets from queries and counterexamples
inferredcites →https://doi.org/10.1016/s0167-5060(04)x8001-8openalex-snapshot
Algorithmic Graph Theory and Perfect Graphs
inferredcites →https://doi.org/10.1016/s0167-5060(08)70731-3openalex-snapshot
Aggregation of Inequalities in Integer Programming
inferredcites →https://doi.org/10.1016/s0304-0208(08)73462-5openalex-snapshot
Threshold Numbers and Threshold Completions
inferredcites →https://doi.org/10.1109/sfcs.1992.267799openalex-snapshot
Read-thrice DNF is hard to learn with membership and equivalence queries
inferredcites →https://doi.org/10.1109/sfcs.1993.366857openalex-snapshot
Exact learning via the Monotone theory
inferredcites →https://doi.org/10.1137/0206008openalex-snapshot
A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
inferredcites →https://doi.org/10.1137/0603036openalex-snapshot
The Complexity of the Partial Order Dimension Problem
inferredcites →https://doi.org/10.1137/s009753979223455xopenalex-snapshot
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain
inferredcites →https://doi.org/10.1145/103418.103420openalex-snapshot
When won't membership queries help?
inferredcites →https://doi.org/10.1145/138027.138042openalex-snapshot
The minimum consistent DFA problem cannot be approximated within any polynomial
inferredcites →https://doi.org/10.1145/138027.138061openalex-snapshot
Learning read-once formulas with queries
inferredcites →https://doi.org/10.1145/174644.174647openalex-snapshot
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
inferredcites →https://doi.org/10.1145/180139.181051openalex-snapshot
On learning Read-k-Satisfy-j DNF
inferredcites →https://doi.org/10.1145/180139.181063openalex-snapshot
On the limits of proper learnability of subclasses of DNF formulas
inferredcites →https://doi.org/10.1145/225058.225114openalex-snapshot
How many queries are needed to learn?
inferredcites →https://doi.org/10.1145/225298.225311openalex-snapshot
Generalized teaching dimensions and the query complexity of learning
inferredcites →https://doi.org/10.1145/28395.28426openalex-snapshot
On the learnability of Boolean formulae
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
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.1997.2684openalex-snapshot
Conjunctions of Unate DNF Formulas: Learning and Structure
inferred← citeshttps://doi.org/10.1006/inco.1997.2687openalex-snapshot
Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions
inferred← citeshttps://doi.org/10.1007/3-540-36169-3_14openalex-snapshot
The Complexity of Learning Concept Classes with Polynomial General Dimension
inferred← citeshttps://doi.org/10.1007/3-540-45841-7_53openalex-snapshot
Learnability and Definability in Trees and Similar Structures
inferred← citeshttps://doi.org/10.1007/3-540-46632-0_27openalex-snapshot
A Linear Time Algorithm for Recognizing Regular Boolean Functions
inferred← citeshttps://doi.org/10.1007/3-540-63577-7_36openalex-snapshot
On exploiting knowledge and concept use in learning theory
inferred← citeshttps://doi.org/10.1007/3-540-63577-7_60openalex-snapshot
On learning disjunctions of zero-one threshold functions with queries
inferred← citeshttps://doi.org/10.1007/978-3-540-39624-6_18openalex-snapshot
On the Complexity of Training a Single Perceptron with Programmable Synaptic Delays
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_35openalex-snapshot
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/bfb0028548openalex-snapshot
On disguised double horn functions and extensions
inferred← citeshttps://doi.org/10.1007/pl00013834openalex-snapshot
PAC Learning Intersections of Halfspaces with Membership Queries
inferred← citeshttps://doi.org/10.1007/s00224-003-1112-8openalex-snapshot
Learnability and Definability in Trees and Similar Structures
inferred← citeshttps://doi.org/10.1007/s00224-013-9488-6openalex-snapshot
Learning Read-Constant Polynomials of Constant Degree Modulo Composites
inferred← citeshttps://doi.org/10.1016/j.artint.2003.04.003openalex-snapshot
Version spaces and the consistency problem
inferred← citeshttps://doi.org/10.1016/j.artint.2004.01.002openalex-snapshot
Theory revision with queries: Horn, read-once, and parity formulas
inferred← citeshttps://doi.org/10.1016/j.jcss.2004.10.001openalex-snapshot
Exact learning of DNF formulas using DNF hypotheses
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.016openalex-snapshot
The complexity of learning concept classes with polynomial general dimension
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.04.034openalex-snapshot
Exact learning from an honest teacher that answers membership queries
inferred← citeshttps://doi.org/10.1016/s0196-6774(02)00003-2openalex-snapshot
A linear time algorithm for recognizing regular Boolean functions
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00003-2openalex-snapshot
Decision lists and related Boolean functions
inferred← citeshttps://doi.org/10.1023/a:1007627028578openalex-snapshot
Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries
inferred← citeshttps://doi.org/10.1080/13532949708454778openalex-snapshot
ITALIAN IDENTITY: CATHOLIC RESPONSES TO SECULARIST DEFINITIONS, c.1910–48
inferred← citeshttps://doi.org/10.1109/ccc.2006.27openalex-snapshot
Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table
inferred← citeshttps://doi.org/10.1137/060664537openalex-snapshot
Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
inferred← citeshttps://doi.org/10.1145/238061.238112openalex-snapshot
Learning conjunctions of two unate DNF formulas (extended abstract)
inferred← citeshttps://doi.org/10.1145/2539126.2539130openalex-snapshot
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1145/267460.267500openalex-snapshot
Generating all maximal independent sets of bounded-degree hypergraphs
inferred← citeshttps://doi.org/10.1145/509907.509976openalex-snapshot
Exact learning of DNF formulas using DNF hypotheses
inferred← citeshttps://doi.org/10.1162/089976605774320601openalex-snapshot
On the Nonlearnability of a Single Spiking Neuron
inferred← citeshttps://doi.org/10.46298/lmcs-19(2:5)2023openalex-snapshot
Inferring Symbolic Automata
inferred← citeshttps://doi.org/10.46298/lmcs-21(3:9)2025openalex-snapshot
Learning Concepts Definable in First-Order Logic with Counting
inferred← citeshttps://doi.org/10.48550/arxiv.1706.01747openalex-snapshot
Specifying a positive threshold function via extremal points
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.