Event Detail

Let N points be chosen at random in some finite domain of the plane. With high probability, for every circle, the proportion of points inside the circle is very close to the area of the circle. (Hence for example a computer can approximately reconstruct a disc given random points inside and outside of it.) This works because the family of discs satisfies a combinatorial property known as finite VC-dimension. This notion originates in machine learning theory: the property described implies that a class of finite VC-dimension is “learnable”. In the first part of my talk, I will present this and state a measure-free analog of this learnability property called the (p,k)-theorem (due to Alon-Kleitman and Matousek).

The definition of finite VC-dimension also appeared independently in model theory under the name NIP (negation of the Independence Property). A formula f(x,y) is NIP if the family of definable sets it defines has finite VC-dimension. In the second part of the talk, I will discuss some interesting consequences of the (p,k)-theorem in model theory and mention open problems.