The Usage of the Spectral Norm in Learning Theory: Some Selected Topics
(invited lecture for ALT 2006)
Author: Hans Ulrich Simon
Affiliation: Fakultät für Mathematik,
Ruhr-Universität Bochum, Germany
In the talk, we review some known results about the statistical query
complexity of a concept class and the spectral norm of its correlation
matrix. Since spectral norms are widely used in various other areas,
we are then able to put statistical query complexity in a broader
context. We briefly describe some surprising connections to (seemingly)
different topics in learning theory, complexity theory, and cryptography.
A connection to the so-called Hidden Number Problem, which plays an
important role for proving bit-security of cryptographic functions,
will be discussed in somewhat more detail.
©Copyright 2006 Author