Sannolikhets- och statistikseminarium: Random sampling in the presence of bounded VC-dimension, for subsets of groups

  • Datum:
  • Plats: Ångströmlaboratoriet 64119
  • Föreläsare: Olof Sisask, Uppsala
  • Kontaktperson: Fiona Skerman
  • Seminarium

Abstract: The VC-dimension of a family sets, named after Vapnik and Chervonenkis, is an interesting combinatorial concept with wide applicability, featuring in probability, machine learning and computational geometry. In this talk we shall discuss a notion of VC-dimension for subsets of groups and discuss the structure of subsets of abelian groups with bounded VC-dimension -- illustrating what might be termed an arithmetic regularity lemma akin to Szemeredi's regularity lemma for graphs. This regularity lemma will actually be a consequence of some analytic results about convolutions, the proofs of which will use methods from probability. Very little background on these topics will be assumed!