On uniform definability of types over finite sets for NIP formulas
Authors:
- 29 December 2020
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Journal of Mathematical Logic
- Vol. 21 (03)
Abstract
Combining two results from machine learning theory we prove that a formula is NIP if and only if it satisfies uniform definability of types over finite sets (UDTFS). This settles a conjecture of Laskowski.Keywords
All Related Versions
Funding Information
- THE ISRAEL SCIENCE FOUNDATION (1533/14, 1254/18)
This publication has 8 references indexed in Scilit:
- Sample Compression Schemes for VC ClassesJournal of the ACM, 2016
- A Guide to NIP Theories2015
- Externally definable sets and dependent pairs IITransactions of the American Mathematical Society, 2015
- On uniform definability of types over finite setsThe Journal of Symbolic Logic, 2012
- A Course in Model Theory2012
- Compression Schemes, Stable Definable Families, and o-Minimal StructuresDiscrete & Computational Geometry, 2009
- Geometric Stability Theory1996
- Zur Theorie der GesellschaftsspieleMathematische Annalen, 1928