Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kattermann, David, Krapp, Lothar Sebastian
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity Logic 8T05, 03D80, 03D25 (Primary) 68Q32, 68T09, 68T27, 68Q04, 03D32 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning Equivalence Relations on Polish Spaces
by: Rossegger, Dino, et al.
Published: (2024)

Strong Kurtz Randomness and Binary Expansions of Reordered Computable Numbers
by: Hertling, Peter, et al.
Published: (2025)

Regainingly approximable numbers and sets
by: Hertling, Peter, et al.
Published: (2023)

Information vs Dimension -- an Algorithmic Perspective
by: Reimann, Jan
Published: (2024)

Solovay reducibility implies S2a-reducibility
by: Titov, Ivan
Published: (2024)

A total Solovay reducibility and totalizing of the notion of speedability
by: Merkle, Wolfgang, et al.
Published: (2024)

On the incomputability of computable dimension
by: Staiger, Ludwig
Published: (2019)

Extending the Limit Theorem of Barmpalias and Lewis-Pye to all reals
by: Titov, Ivan
Published: (2024)

Why the classes P and NP are not well-defined finitarily
by: Anand, Bhupinder Singh
Published: (2024)

Hallucination, abstention, and computable inseparability
by: Imamura, Takuma
Published: (2026)

Variants of Solovay reducibility
by: Titov, Ivan
Published: (2024)

Uniformity in learning structures
by: Cipriani, Vittorio, et al.
Published: (2025)

Classifying different criteria for learning algebraic structures
by: Bazhenov, Nikolay, et al.
Published: (2024)

On the learning power of Friedman-Stanley jumps
by: Cipriani, Vittorio, et al.
Published: (2025)

Choiceless Polynomial Space
by: Ferrarotti, Flavio, et al.
Published: (2024)

Finitely Bounded Homogeneity Turned Inside-Out
by: Rydval, Jakub
Published: (2021)

Refutability as Recursive as Provability
by: Cattabriga, Paola
Published: (2024)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

A Minimal Substitution Basis for the Kalmár Elementary Functions
by: Prunescu, Mihai, et al.
Published: (2025)

Quantum Random Self-Modifiable Computation
by: Fiske, Michael Stephen
Published: (2018)

Languages given by Finite Automata over the Unary Alphabet
by: Czerwiński, Wojciech, et al.
Published: (2023)

Resource bounded Kučera-Gács Theorems
by: Nandakumar, Satyadev, et al.
Published: (2026)

Approximability of deep computations
by: Alva, Samson, et al.
Published: (2024)

Bounds on the dimension of lineal extensions
by: Bushling, Ryan E. G., et al.
Published: (2024)

Randomness, exchangeability, and conformal prediction
by: Vovk, Vladimir
Published: (2025)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

The Optimizer Quotient and the Certification Trilemma
by: Simas, Tristan
Published: (2026)

On Chaitin's Heuristic Principle and Halting Probability
by: Salehi, Saeed
Published: (2023)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Provability in BI's Sequent Calculus is Decidable
by: Gheorghiu, Alexander, et al.
Published: (2021)

There is a deep 1-generic set
by: Li, Ang
Published: (2024)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem
by: Brossard, Jonathan
Published: (2026)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

Uniform Computability of PAC Learning
by: Brattka, Vasco, et al.
Published: (2026)

Truth-Aware Decoding: A Program-Logic Approach to Factual Language Generation
by: Alpay, Faruk, et al.
Published: (2025)

Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization
by: Boche, Holger, et al.
Published: (2024)

Computational Complexity of Model-Checking Quantum Pushdown Systems
by: Lin, Deren, et al.
Published: (2025)