Mathematics Class of 1960s Speaker: Prof. Alex Iosevich, University of Rochester

Fri, September 24th, 20211:00 pm - 1:50 pm

Mathematics Class of 1960s Speaker: Prof. Alex Iosevich, University of Rochester, The Vapnik-Chervonenkis Dimension and the Structure of Point Configurations in Vector Spaces Over Finite Fields, 1 – 2:00 pm, Wachenheim 116

Abstract: Let X be a set and let H be a collection of functions from X to {0,1}.  We say that H shatters a finite subset C of X if the restriction of H yields every possible function from C to {0,1}.  The VC-dimension of H is the largest number d such that there exists a set of size d shattered by H, and no set of size d + 1 is shattered by H.  Vapnik and Chervonenkis introduced this idea in the early 70s in the context of learning theory, and this idea has also had a significant impact on other areas of mathematics.  In this paper, we study the VC-dimension of a class of functions H defined on Fqd, the d-dimensional vector space over the finite field with q elements.  Define

Htd = {hy(x) : y is in Fqd},

where for x in Fqd, hy(x) = 1 if ||x – y|| = t, and 0 otherwise, where here, and throughout, ||x|| = x12 + x22 + … + xd2.  Here t is a nonzero element of Fq.  Define Htd(E) the same way with respect to E, a subset of Fqd. The learning task here is to find a sphere of radius t centered at some point y in E unknown to the learner.  The learning process consists of taking random samples of elements of E of sufficiently large size.

We are going to prove that when d = 2, and |E| is greater than or equal to Cq(15/8), the VC-dimension of Ht2(E) is equal to 3.  This leads to an intricate configuration problem which is interesting in its own right and requires a new approach.