Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, February 24, 2014 - 3:00pm

David Lippel

Haverford College

Location

University of Pennsylvania

2C4

Let F be a family of sets, for example, a uniformly definable semi-algebraic family in real or p-adic n-space. The Vapnik-Chervonenkis (VC) dimension of F is a measurement of the combinatorial complexity of F. Once you know the VC dimension of F, theorems from computational geometry, like the Epsilon- Net Theorem, give nice geometric consequences for F. After introducing VC dimension and the Epsilon-Net Theorem, I will discuss a statistical strategy for reversing the flow of information in this theorem. Instead of starting with knowledge of the VC dimension, we merely hypothesize "dimension=d" for some value d. Then, we observe the geometric behavior of F using computer experiments and compare the observed behavior with the behavior that is predicted by the theorem (under the hypothesis "dimension=d"). If our observed results have sufficiently low probability (conditioned on "dimension=d"), then we can reject the hypothesis "dimension=d" with a high degree of confidence. Ultimately, we hope to use such methods to shed light on conjectures about VC density in the p-adics. This project is joint work with Deirdre Haskell and Nigel Pynn-Coates.