MODNET

Research Training Network in Model Theory

Publications > Preprint server > Preprint Number 1824
Preprint Number 1824
1824. Bjarki Geir Benediktsson, Dugald Macpherson, Isolde Adler Vapnik-Chervonenkis Dimension and Density on Johnson and Hamming Graphs E-mail: Submission date: 31 July 2020 Abstract: VC-dimension and VC-density are measures of combinatorial complexity of set
systems. VC-dimension was first introduced in the context of statistical
learning theory, and is tightly related to the sample complexity in PAC
learning. VC-density is a refinement of VC-dimension. Both notions are also
studied in model theory, in the context of \emph{dependent} theories. A set
system that is definable by a formula of first-order logic with parameters has
finite VC-dimension if and only if the formula is a dependent formula. Mathematics Subject Classification: Keywords and phrases: |

Last updated: August 5 2020 09:51 | Please send your corrections to: |