Compression schemes, stable definable families, and o-minimal structures

DOI10.1007/s00454-009-9201-3zbMath1201.03022OpenAlexW1978484169MaRDI QIDQ972602

Hunter Johnson, Michael Chris Laskowski

Publication date: 21 May 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-009-9201-3

zbMATH Keywords

stabledensityVC dimensioncombinatorial complexityNIPdependenceUDTFSo-minimalcompression schemedefinable typeindependence dimensiontype definitionUFTDWarmuth conjecture

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Learning and adaptive systems in artificial intelligence (68T05) Extremal set theory (05D05) Model theory of ordered structures; o-minimality (03C64)

Related Items (8)

On uniform definability of types over finite sets ⋮ RAMSEY GROWTH IN SOME NIP STRUCTURES ⋮ 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10 ⋮ On uniform definability of types over finite sets for NIP formulas ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ VC density of definable families over valued fields ⋮ MODEL THEORY AND MACHINE LEARNING ⋮ Externally definable sets and dependent pairs II

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\epsilon\)-nets and simplex range queries
• Classification theory and the number of non-isomorphic models.
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Density and dimension
• A theorem of the complement and some new o-minimal structures
• Projections of semi-analytic sets
• Vapnik-Chervonenkis Classes of Definable Sets
• Uniform Central Limit Theorems
• 10.1162/jmlr.2003.3.4-5.723
• Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function

This page was built for publication: Compression schemes, stable definable families, and o-minimal structures