DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.72

Local Combinatorial Analogues for Bounded VC Dimension

Authors: Olga Medrano Martín del Campo

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

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.

Cite as

Olga Medrano Martín del Campo. Local Combinatorial Analogues for Bounded VC Dimension. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 72:1-72:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{medranomartindelcampo:LIPIcs.LICS.2026.72,
  author =	{Medrano Mart{\'\i}n del Campo, Olga},
  title =	{{Local Combinatorial Analogues for Bounded VC Dimension}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{72:1--72:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.72},
  URN =		{urn:nbn:de:0030-drops-268591},
  doi =		{10.4230/LIPIcs.LICS.2026.72},
  annote =	{Keywords: Littlestone, Vapnik-Chervonenkis, good sets, Regularity Lemma, Haussler Packing Lemma, Fundamental Theorem of Statistical Learning}
}

Search Results

Documents authored by Medrano Martín del Campo, Olga

Local Combinatorial Analogues for Bounded VC Dimension

Abstract

Cite as

Thanks for your feedback!

Could not send message