Rocco Servedio, Learning, Testing, and Approximation

Abstract:
Roughly speaking, in learning theory the goal is to use limited data
to construct an approximation to an unknown function, and in property
testing the goal is to determine whether an unknown function can be
approximated in a particular way using very limited access to the
function.  Thus it is clear that (at least on a superficial level)
both learning and testing are closely connected to approximation.

The high-level goal of this talk is to demonstrate that in fact
deeper connections exist between these topics.  Each of these three
tasks -- learning, testing, and approximation -- can be viewed as a
type of "lens" for gaining insights into classes of functions, and
the insights gained from one viewpoint can quite often be profitably
transferred to the other tasks.  We demonstrate this by describing
recent results that connect learning, testing, and approximation for
many different well-studied types of Boolean functions, such as DNF
formulas, decision trees, sparse polynomials, and halfspaces.

The talk is based in part on joint work with I. Diakonikolas, H. Lee,
K. Matulef, K. Onak, R. Rubinfeld and A. Wan; with K. Matulef, R.
Rubinfeld and R. O'Donnell; and with R. O'Donnell.