Paper: Local Combinatorial Analogues for Bounded VC Dimension (at LICS 2026)

Authors: Olga Medrano Martín del Campo

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.72

Abstract

Stable graphs, or equivalently Littlestone classes, were characterized by existence of linear-sized "good" sets, a kind of strongly homogeneous set, in work of Malliaris-Shelah and Malliaris-Moran. We prove a parallel result for VC classes, showing these are characterized by existence of linear-sized symmetric or asymmetric good pairs (which we define). We give several proofs, each drawing from methods and results from different areas, and resulting in different kinds of bounds. We finish with a few words on our learning theory motivation for these investigations and state some further research directions.

BibTeX

  @InProceedings{MedranoMartindelCam-LocalCombinatorialA,
    author = 	 {Olga Medrano Martín del Campo},
    title = 	 {Local Combinatorial Analogues for Bounded VC Dimension},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {72:1--72:22},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.72}
  }