**Rocco Servedio, Learning, Testing, and Approximation
**

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.