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.