Pith. sign in

REVIEW 3 major objections 5 minor 40 references

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

T0 review · 3 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Computable PAC learning does not inherit the classical Fundamental Theorem: for any k ≤ ℓ, an algorithmically listable class can have VC-dimension k and effective VC-dimension ℓ.

desk verdict Solid, useful paper: it fills the gap between VCdim and eVCdim for all pairs k≤ℓ on RER classes and shows every RER class is properly nonuniformly CPAC learnable; the main weakness is that several supporting proofs live in the first author's master's thesis rather than the preprint. read the letter →

arxiv 2511.02644 v2 pith:JUOXCHJU submitted 2025-11-04 cs.LG cs.CCmath.LO

David Kattermann , Lothar Sebastian Krapp This is my paper · ORCID
classification cs.LGcs.CCmath.LO MSC 68T0503D8003D2568Q3268T0968T2768Q0403D32
keywords computablePAClearningeffectiveVC-dimensionRERclassesnonuniformstructuralriskminimizationuniqueidentificationpropertyagnostic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper maps exactly how the Fundamental Theorem of Statistical Learning breaks when learners must be computable. Its central result is a construction: for every pair 1 ≤ k ≤ ℓ ≤ ∞, there is a hypothesis class that can be algorithmically listed (an RER class) whose ordinary VC-dimension is k and whose effective, computable VC-dimension is ℓ. Thus the effective dimension is not just sometimes larger; it can be tuned to any value above the classical one, even under listability and finite-support assumptions. On the other side, the paper proves that every RER class is properly learnable in the relaxed agnostic sense of nonuniform CPAC learning, with a computable structural risk minimizer, regardless of either dimension. The upshot is a precise division: listability alone does not restore the classical theorem, but computable empirical risk minimization and nonuniform learning do.

What carries the argument

The load-bearing objects are: (i) the direct sum of hypothesis classes with disjoint supports, whose VC-dimension is claimed to add (Lemma 3.1); (ii) the RER class of all finitely supported hypotheses with a computable list representation, which supplies the ambient decidability; (iii) halting-based hypotheses h_e that place a 1 at a unique odd marker u_e and read off block labels from the halting output of machine T_e, making computable witnesses fail by diagonalization; and (iv) structural risk minimization with weight ω(n) = 2n² and error ε(m,b) = √(b/2m), whose computable minimizer yields the nonuniform learner.

What would settle it

Run the construction for k = 1, ℓ = 2 and search for a computable 1-witness for H_{1,2}; finding one would refute the claimed eVCdim = 2. More directly, exhibit two finite hypothesis classes G and H with disjoint supports for which VCdim(G ⊕ H) ≠ VCdim(G) + VCdim(H); that single counterexample refutes Lemma 3.1 and with it the proof of Theorem 3.2.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is Theorem 3.2: for every 1 ≤ k ≤ ℓ ≤ ∞ there exists an RER class H_{k,ℓ} contained in the finitely supported hypotheses such that VCdim(H_{k,ℓ}) = k and eVCdim(H_{k,ℓ}) = ℓ. The construction splits the domain into a fixed k−1 point block and computably many disjoint blocks indexed by Turing machines; each block's labels are the output of a machine that halts, with a unique odd marker marking the block. Membership in the class is decidable from the list representation of the class of all finitely supported hypotheses, so the class is RER, and a diagonalization in step V shows no computable witness of size ℓ−1 can exist. The paper also proves Propos

Load-bearing premise

The arbitrary-gap theorem rests on Lemma 3.1, stated without proof and deferred to a companion thesis, that VC-dimension adds across disjointly supported direct sums—and, in the lower bound, on an acceptable Gödel numbering—so if either gives way the claimed gap collapses.

Editorial extensions

If this is right

  • The family H_{k,ℓ} yields a complete table of non-equivalences: when k < ℓ < ∞ the class is agnostically CPAC learnable but not properly agnostically strongly CPAC learnable; when ℓ = ∞ it is not agnostically CPAC learnable at all.
  • A total computable empirical risk minimizer forces the two dimensions to coincide, so restoring the classical characterization in the computable setting requires computable optimization, not merely computable listing.
  • Proper SCPAC learnability is equivalent to the existence of an RER subclass with the same realized samples, so every counterexample to the converse must be an extension of an RER class that adds hypotheses without adding new realizable samples.
  • For classes with the unique identification property, realizable CPAC learnability collapses to the RER property plus finite VC-dimension, giving a full analog of the Fundamental Theorem in that setting.
  • Every RER class, no matter its dimensions, is properly nonuniformly CPAC learnable; hence the agnostic barrier is not learnability itself but the demand for a single uniform sample-complexity bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The theorem's only unproved local input, Lemma 3.1, is doing real work: if additivity of VC-dimension under direct sums of disjointly supported classes fails, the claimed equality VCdim(H_{k,ℓ}) = k falls with it. A direct proof of the lemma would remove the paper's main caveat.
  • The construction suggests a design principle: whether a computable learning guarantee holds is governed more by the complexity of empirical-risk minimization than by the complexity of listing the class. This is an editorial inference, not a thesis stated by the paper.
  • The SRM proof yields an explicit polynomial sample-complexity bound in a, b, and the index n_h of the hypothesis; treating that quantitative bound as a formal theorem would give practitioners a concrete curve for nonuniform computable learning.
  • The paper leaves open whether any CPAC-learnable class contains an uncomputable hypothesis; a negative answer would imply that learnable classes are effectively listable in a strong sense and would sharpen the boundary between computable and uncomputable hypotheses.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies computable PAC (CPAC) learning, the effective VC-dimension, and recursively enumerably representable (RER) hypothesis classes. The central contributions are: (1) Theorem 3.2, which constructs, for every 1 ≤ k ≤ ℓ ≤ ∞, an RER class H_{k,ℓ} ⊆ H_fin with VCdim(H_{k,ℓ}) = k and eVCdim(H_{k,ℓ}) = ℓ, showing that the effective VC-dimension can be arbitrarily larger than the classical one even for algorithmically listable classes; (2) Proposition 3.3, which shows that existence of a total computable ERM forces equality of the two dimensions; (3) Section 4, which characterizes proper strong CPAC learnability via containment of an RER subclass realizing the same samples, and proves that unique-identification (UIP) classes that are realizably CPAC learnable must be RER; and (4) Theorem 5.3, which shows that every RER class is properly nonuniformly CPAC learnable via a computable structural risk minimizer. The proofs are constructive and, for the main theorems, internally consistent; the primary weakness is the deferral of several supporting results to the first author's unpublished master's thesis [K25].

Significance. If the results stand, they substantially clarify the computable-learning landscape. The construction in Theorem 3.2 rules out any general relationship between VCdim and eVCdim beyond the trivial inequality, even under the strong RER and finite-support assumptions; this is a meaningful sharpening of the earlier example of Delle Rose et al. with VCdim 1 and eVCdim ∞. Proposition 3.3 identifies a clean sufficient condition for equality. The RER-based characterizations in Section 4 give a useful sample-realization perspective on proper SCPAC learnability, and the SRM construction in Section 5 shows that the RER property alone guarantees a relaxed agnostic learnability notion. The paper is careful with the many variants of PAC learning, provides a helpful table of notions, and is honest about which auxiliary results are deferred. The main mathematical claims are plausible and the proofs of Theorems 3.2, 4.2, and 5.3 are detailed enough to be checked. The main deficit is not correctness but self-containedness: several load-bearing lemmas and corollaries are relegated to [K25], which is not a peer-reviewed publication.

major comments (3)
  1. [§3, Lemma 3.1] The computation VCdim(H_{k,ℓ}) = k in Theorem 3.2 rests entirely on Lemma 3.1, which is stated without proof and deferred to [K25, Lemma 3.51]. Since [K25] is an unpublished master's thesis, this is a load-bearing gap in an otherwise self-contained proof. The lemma is elementary, but the reader should not have to consult an external thesis to verify the central claim. Please include a proof, or at least a complete proof sketch, in the paper.
  2. [§5, Lemma 5.2 and Theorem 5.3] The proof of Theorem 5.3 relies on the SRM guarantee (5.6), which is stated as 'one can show' and deferred to [K25, Lemma 4.14]. This inequality is the central mechanism that converts a computable SRM into a nonuniform PAC learner, so it is load-bearing. The proof is not long and should be included. Similarly, the realizable version of Fact 2.8 used in Theorem 4.2 is deferred to [K25, p. 65ff]; please include that argument as well.
  3. [§4, Remark 4.4 / Corollary 4.5 and §5, Corollary 5.8] Several results used in the paper's summary and Table 3 are deferred to [K25]: the non-strong CPAC analog in Remark 4.4, Corollary 4.5 ('For a full proof see [K25, Corollary 3.58]'), and Corollary 5.8 ('See [K25, Proposition 4.23] for details'). These are not merely peripheral: Corollary 4.5 is stated as a characterization of agnostic CPAC learnability and Corollary 5.8 as a necessary condition for nonuniform CPAC learnability. For archival publication, these should be proved in the text or replaced by references to published, accessible sources.
minor comments (5)
  1. [References] In the bibliography, the second author of [BS14] is spelled 'Shalez-Shwartz'; this should be 'Shalev-Shwartz'.
  2. [Definition 2.6] The phrase 'a computable function A′:N⇀N of A' is awkward; it should say 'a computable function A′ representing A' or 'such that A′ computes A'.
  3. [§3, Step I] In the enumeration of pairs ((T_j, k_j)), saying that 'the maps j↦code(T_j) and j↦k_j are computable' is redundant once a computable enumeration is fixed; consider simplifying the phrasing.
  4. [Lemma 4.7] In the proof, the line 'Prob ≥ 1/2 > 0' implicitly uses the realizable PAC guarantee with confidence parameter b = 2. This is correct but should be stated explicitly to avoid confusion.
  5. [Definition 2.3] The witness-based definition of VC-dimension is nonstandard. A one-sentence explanation of its equivalence to the usual shattering definition would improve readability for readers more familiar with the standard formulation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central constructions and theorems are derived from definitions and external results; self-citations to [K25] are auxiliary and non-load-bearing.

full rationale

Walking the derivation chain, no load-bearing step reduces to its own input by construction. Theorem 3.2 is a genuine diagonalization: the class H_{k,ℓ} is built from a computable enumeration E of halting machines; VCdim(H_{k,ℓ}) = k uses Lemma 3.1 (disjoint-support additivity), which is stated in the paper as a definition-level fact and is independent of the conclusion, and eVCdim(H_{k,ℓ}) ≤ ℓ and ≥ ℓ are direct computable-witness and diagonalization arguments, not fitted values. Proposition 3.3 constructs a computable k-witness from a total computable ERM; no ERM parameter is later renamed as a prediction. Theorem 4.2/Corollary 4.3 derive RER containments from the image of a computable learner (Lemma 4.1) plus Fact 2.8 (Sterkenburg), an external published result. Theorem 5.3 uses a standard SRM/Hoeffding argument with a computable minimizer; the bound is derived, not assumed. The only caveat is that several supporting proofs (e.g., Lemma 3.1, Corollaries 4.5 and 5.8, and details in Remarks 4.4 and 5.7) are deferred to the first author's thesis [K25]; this is a verifiability and self-citation concern, but not circularity: the lemma statements are given, their assumptions do not include the target results, and the central claims do not reduce to [K25]. No circular reduction exists, so the score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

This is a pure-mathematics paper: it introduces no fitted parameters and no new postulated entities. Its load-bearing assumptions are the standard model of computability, the restriction to countable domains, prior theorems from the CPAC literature, and one unproved VC-dimension lemma deferred to the first author's thesis.

assumptions (5)
  • standard math Church–Turing thesis / standard Turing-machine model of computability (Section 2, Definition 2.6)
    The definitions of computable learner, RER classes, and effective VC-dimension assume the standard notion of computability via Turing machines and acceptable Gödel numberings. This is a background assumption of the subfield, not introduced ad hoc.
  • domain assumption Countable/encodable domain X ⊆ N with powerset σ-algebra (Section 2)
    The paper restricts to countable domains so that every hypothesis is measurable and the classical well-behavedness condition can be ignored. The proof of Theorem 2.5's footnote and the setup in Section 2 make this explicit.
  • standard math Prior theorems: S22 Theorem 8 (proper SCPAC), DKR+23 Theorem 3 (agnostic CPAC via eVCdim), AAB+20 Theorem 10 (RER classes)
    These black-box results from the cited literature underpin Theorem 4.2, Corollary 4.3, and Table 2. They are treated as established background, not re-derived.
  • standard math Lemma 3.1: VCdim(G ⊕ H) = VCdim(G) + VCdim(H) for disjoint-support G,H
    Stated in Section 3 without proof, deferred to [K25, Lemma 3.51]. Used to compute VCdim(H_{k,ℓ}) = k in Theorem 3.2. This is the most fragile unproved ingredient.
  • standard math Hoeffding's inequality (Theorem 5.3)
    Used to verify SRM condition (5.4) in the proof of Theorem 5.3. Standard concentration inequality, accepted as known.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning." pith.science (2026). https://pith.science/paper/JUOXCHJU

@misc{pith2026251102644,
  author       = {Pith},
  title        = {Pith review of: Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JUOXCHJU}},
  note         = {Machine review of arXiv:2511.02644}
}
read the original abstract

We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Statistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Fundamental Theorem in the computable setting, for instance by introducing an effective VC-dimension. Guided by this, we investigate the connection between CPAC learning and recursively enumerable representable (RER) classes, whose members can be algorithmically listed. Our results show that the effective VC-dimensions can take arbitrary values above the traditional one, even for RER classes, which creates a whole family of (non-)examples for various notions of CPAC learning. Yet the two dimensions coincide for classes satisfying sufficiently strong notions of CPAC learning. We then observe that CPAC learnability can also be characterized via containment of RER classes that realize the same samples. Furthermore, it is shown that CPAC learnable classes satisfying a unique identification property are necessarily RER. Finally, we establish that agnostic learnability can be guaranteed for RER classes, by considering the relaxed notion of nonuniform CPAC learning.

Figures

Figures reproduced from arXiv: 2511.02644 by the authors.

Figure 1
Figure 1. Equivalences from the Fundamental Theorem of Statistical Learning [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Relationship between CPAC learning and the RER property. To conclude, we collect some questions from the field of CPAC learning that could not be answered in this paper. Theorem 3.2 showed that the effective VC-dimension can take arbitrary values between 1 and infinity for RER classes, which by definition only contain computable hypotheses. It is also evident that eVCdim(H) = 0 if and only if H = {h} for some comput… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 2 canonical work pages

  1. [1]

    Agarwal, A

    A. Agarwal, A. Ananthakrishnan, S. Ben-David, T. Lechner, R. Urner: On Learnability with Computable Learners. Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:48-60, 2020

    2020

  2. [2]

    Agarwal, A

    A. Agarwal, A. Ananthakrishnan, S. Ben-David, T. Lechner, R. Urner: Open Problem: Are all VC-classes CPAC learnable? Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4636-4641, 2021

    2021

  3. [3]

    Ackerman, J

    N. Ackerman, J. Asilis, J. Di, C. Freer, J.-B. Tristan: Computable learning of continuous features. Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Article 7, 2022

    2022

  4. [4]

    Ackermann: Zum Hilbertschen Aufbau der reellen Zahlen

    W. Ackermann: Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen, Band 99 (1928)

    1928

  5. [5]

    Akbari, M

    S. Akbari, M. Harrison-Trainor: Computable learning of natural hypothesis classes. Proceedings of 38th Conference on Learning Theory, PMLR 291:2-21, 2025

    2025

  6. [6]

    N. Alon, S. Hanneke, R. Holzman, S. Moran: A Theory of PAC Learnability of Partial Concept Classes. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), doi:10.1109/FOCS52979.2021.00070 https://doi.org/10.1109/FOCS52979.2021.00070

    arXiv 2021

  7. [7]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler and M. K. Warmuth: Learnability and the Vapnik-Chervonenkis Dimension. J. Assoc. Comput. Mach. 36 (1989) 929–965

    1989

  8. [8]

    Boche, V

    H. Boche, V. Fojtik, A. Fono, G. Kutyniok: Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization. arXiv preprint, https://arxiv.org/abs/2408.06212 (2024)

    arXiv 2024

Show all 40 references
  1. [9]

    Ben-David, N

    S. Ben-David, N. Hasrati: On Computable Online Learning. Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:707-725, 2023

    2023

  2. [10]

    Ben-David, P

    S. Ben-David, P. Hrubes, S. Moran, A. Shpilka, A. Yehudayoff: Learnability can be undecidable. Nature Machine Intelligence Vol. 1, 44–48, 2019, doi:10.1038/s42256-018-0002-3 https://doi.org/10.1038/s42256-018-0002-3

    2019 doi

  3. [11]

    Bousquet, S

    O. Bousquet, S. Hanneke, S. Moran, R. van Handel, A. Yehudayoff: A Theory of Universal Learning. arXiv preprint, https://arxiv.org/abs/2011.04483v1 (2020)

    2011 arXiv

  4. [12]

    Brattka, P

    V. Brattka, P. Hertling (Editors): Handbook of Computability and Complexity in Analysis. Springer Nature (2021)

    2021

  5. [13]

    Benedek, A

    G. Benedek, A. Itai: Nonuniform Learnability. J. Comput. Syst. Sci. 48, 1994, doi:10.1016/S0022-0000(05)80005-4 https://doi.org/10.1016/S0022-0000(05)80005-4

    1994 doi

  6. [14]

    Ben-David, S

    S. Ben-David, S. Shalez-Shwartz: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, 2014, doi:10.1017/CBO9781107298019 https://doi.org/10.1017/CBO9781107298019

    2014 doi

  7. [15]

    M. C. Caro: From undecidability of non-triviality and finiteness to undecidability of learnability. International Journal of Approximate Reasoning 163, 2023, doi:10.1016/j.ijar.2023.109057 https://doi.org/10.1016/j.ijar.2023.109057

    2023

  8. [16]

    Crook, J

    T. Crook, J. Morgan, A. Pauly, M. Roggenbach: A Computability Perspective on (Verified) Machine Learning. https://arxiv.org/abs/2102.06585 (2021)

    2021 arXiv

  9. [17]

    Delle Rose, A

    V. Delle Rose, A. Kozachinskiy, C. Rojas, T. Steifer: Find a witness or shatter: the landscape of computable PAC learning. Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:511-524, 2023

    2023

  10. [18]

    Delle Rose, A

    V. Delle Rose, A. Kozachinskiy, T. Steifer: Effective Littlestone Dimension. Proceedings of Machine Learning Research Vol. 272:1–13, 2025

    2025

  11. [19]

    Downey, A

    R. Downey, A. Melnikov: Computably Compact Metric Spaces. The Bulletin of Symbolic Logic Volume 20(2) (2023)

    2023

  12. [20]

    Downey, A

    R. Downey, A. Melnikov: Comptuable Structure Theory: A Universal Approach. (to appear) https://homepages.ecs.vuw.ac.nz/ melnikal/maindoc.pdf (2024)

    2024

  13. [21]

    Goldman, M.J

    S.A. Goldman, M.J. Kearn: On the complexity of teaching. J. Comput. Syst. Sci. 50, 1995, doi:10.1006/jcss.1995.1003 https://doi.org/10.1006/jcss.1995.1003

    1995

  14. [22]

    Gourdeau, T

    P. Gourdeau, T. Lechner, R. Urner: On the Computability of Robust PAC Learning. Proceedings of Machine Learning Research Vol. 196:1–30, 2024

    2024

  15. [23]

    Gourdeau, T

    P. Gourdeau, T. Lechner, R. Urner: On the Computability of Multiclass PAC Learning. arXiv preprint, 2025, https://arxiv.org/abs/2502.06089

    2025 arXiv

  16. [24]

    Hoyrup, C

    M. Hoyrup, C. Rojas: Computability of probability measures and Martin-Lof randomness over metric spaces. arXiv preprint, https://arxiv.org/abs/0709.0907 (2007)

    2007 arXiv

  17. [25]

    Springer-Vieweg (2014)

    J.Hromkovic: Theoretische Informatik: Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie. Springer-Vieweg (2014)

    2014

  18. [26]

    Kearns, U

    M. Kearns, U. Vazirani: An Introduction to Computational Learning Theory. MIT Press (1994)

    1994

  19. [27]

    Kattermann: Computability aspects in statistical learning

    D. Kattermann: Computability aspects in statistical learning. Master's thesis, Universität Konstanz, 2025, http://nbn-resolving.de/urn:nbn:de:bsz:352-2-nbxfk51kav277

    2025

  20. [28]

    L. S. Krapp, L. Wirth: Measurability in the Fundamental Theorem of Statistical Learning. arXiv preprint, 2024, https://arxiv.org/abs/2410.10243

    2024

  21. [29]

    L. Pitt, L. G. Valiant: Computational limitations on learning from examples. Journal of the ACM (JACM), Volume 35, Issue 4, Pages 965 - 984, 1988, doi:10.1145/48014.63140 https://doi.org/10.1145/48014.63140

    1988

  22. [30]

    Schaefer: Deciding the Vapnik–Cervonenkis dimension is _3^p -complete

    M. Schaefer: Deciding the Vapnik–Cervonenkis dimension is _3^p -complete. Journal of Computer and System Sciences, 58(1):177–182, (1999)

    1999

  23. [31]

    Schoening: Theoretische Informatik - kurz gefasst

    U. Schoening: Theoretische Informatik - kurz gefasst. 5. Auflage, Spektrum Verlag Heidelberg (2008)

    2008

  24. [32]

    Smullyan: Recursion Theory for Metamathematics

    R.M. Smullyan: Recursion Theory for Metamathematics. Volume 22 of Oxford Logic Guides. Oxford University Press (1993)

    1993

  25. [33]

    Soare: Turing Computability: Theory and Applications

    R. Soare: Turing Computability: Theory and Applications. Springer-Verlag Berlin, 2016

    2016

  26. [34]

    Spelda, V

    T. Spelda, V. Stritecky: Learnability of state spaces of physical systems is undecidable. Journal of Computational Science 83 (2024)

    2024

  27. [35]

    Sterkenburg: On characterizations of learnability with computable learners

    T. Sterkenburg: On characterizations of learnability with computable learners. Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3365-3379, 2022

    2022

  28. [36]

    Thewmorakot: Computability Theory on Polish Metric Spaces

    T. Thewmorakot: Computability Theory on Polish Metric Spaces. The Bulletin of Symbolic Logic. 29(4) (2023)

    2023

  29. [37]

    Turing: On computable numbers with an application to the Entscheidungsproblem

    A. Turing: On computable numbers with an application to the Entscheidungsproblem. Proc. London Math. Society (2) 43, 1936

    1936

  30. [38]

    L. G. Valiant: A theory of the learnable. Communications of the ACM, Volume 27, Issue 11 Pages 1134 - 1142, 1984, doi:10.1145/1968.1972 https://doi.org/10.1145/1968.1972

    1984

  31. [39]

    V. N. Vapnik, A. Ja. Červonenkis: Uniform Convergence of Frequencies of Occurrence of Events to Their Probabilities. Dokl. Akad. Nauk SSSR 181 (1968) 781–783 (Russian), Sov. Math., Dokl. 9 (1968) 915–918 (English)

    1968

  32. [40]

    Weihrauch: Computability

    K. Weihrauch: Computability. Springer-Verlag Berlin (1987)

    1987

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.