Mathematics Class of 1960s Speaker: Prof. Alex Iosevich, University of Rochester
Fri, September 24th, 2021
1:00 pm  1:50 pm
Mathematics Class of 1960s Speaker: Prof. Alex Iosevich, University of Rochester, The VapnikChervonenkis 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 VCdimension 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 VCdimension of a class of functions H defined on F_{q}^{d}, the ddimensional vector space over the finite field with q elements. Define
H_{t}^{d} = {h_{y}(x) : y is in F_{q}^{d}},
where for x in F_{q}^{d}, h_{y}(x) = 1 if x – y = t, and 0 otherwise, where here, and throughout, x = x_{1}^{2} + x_{2}^{2} + … + x_{d}^{2}. Here t is a nonzero element of F_{q}. Define H_{t}^{d}(E) the same way with respect to E, a subset of F_{q}^{d}. 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 VCdimension of H_{t}^{2}(E) is equal to 3. This leads to an intricate configuration problem which is interesting in its own right and requires a new approach.
Event/Announcement Navigation
Related Events

Log Lunch is Back! Center for Environmental Studies Local Food Lunch Speaker Series: Every Friday
Fri, September 17th, 2021
12:00 pm  1:00 pm
Main Social Nav