Traditional and not-so-Traditional Applications of VC-dimension and its Generalizations

Leonid Gurvits (NECI,Princeton and DIMACS,Rutgers,gurvits@research.nj.nec.com)



In a first part of the talk I will discuss briefly traditional
applications of VC-dimension: uniform laws in statistics and why
VC-dimension is so crucial for the Learning in a PAC setting.

In a second(larger) part , I will discuss, among not-so-traditional
applications, connections between VC-dimension and its real-valued
generalizations to interpolations, graph theory, approximation,
functional analysis, control theory, measure theory, infinite
combinatorics and analysis of stoping times of some algorithms.

Also,I will present one general idea how to bound scale-sensitive
dimension using Moments Inequalities.