Title: Learning, Testing and Approximating Halfspaces Speaker: Rocco Servedio, Columbia Univ. Abstract: A halfspace is a Boolean function of the form f(x) = sign(w.x - theta). Halfspaces (also known as linear threshold functions, weighted majority functions, threshold gates, etc.) are a simple, natural and well-studied class of functions with many applications in fields such as learning theory and complexity theory. We describe recent results on approximating, testing, and learning halfspaces over the Boolean cube {+1,-1\}^n. In more detail, (1) Every halfspace can be approximated by a halfspace with small integer weights; (2) There is an efficient algorithm for testing whether an unknown Boolean function is a halfspace (versus far from every halfspace); (3) Halfspaces can be efficiently approximately reconstructed from approximations to their degree-0 and degree-1 Fourier coefficients (this corresponds to an efficient learning algorithm in the "restricted focus of attention" learning model). This gives a robust and algorithmic version of Chow's theorem on halfspaces from FOCS 1961. The talk will emphasize the connections between these three results.