{"id":"arxiv/2605.13840","url":"https://arxiv.org/abs/2605.13840","tags":["stat.ML","cs.DS","cs.LG","math.ST","stat.CO"],"score":0,"title":"What is Learnable in Valiant's Theory of the Learnable?","domain":"stat.ML","source":"arxiv","authors":["Steve Hanneke","Anay Mehrotra","Grigoris Velegkas","Manolis Zampetakis"],"reviews":0,"subject":"stat.ML","summary":"Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: *Which classes are learnable in it?* For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-05-13","reactions":{}}