Learning a halfspace is one of the oldest and most fundamental tasks in machine learning. It is the essential underlying algorithm for many systems used by practitioners from fields such as artificial intelligence, statistics, and computational biology to classify data. In this talk we will give several new approaches for learning halfspaces and describe surprising algorithmic applications.

First, we will show that learning a halfspace in high dimensions yields fast algorithms for learning Boolean concept classes such as DNF formulae, one of the major challenges in computational learning theory. To this end we will show how to obtain the fastest known DNF learning algorithm.

Secondly, we will describe two new algorithms for learning intersections of halfspaces. Intersections of halfspaces are a powerful concept class; any convex body can be expressed as an intersection of halfspaces, and little is known about the complexity of learning the intersection of even two halfspaces. We give the first polynomial-time algorithms for learning the intersection of any constant number of halfspaces assuming either a margin separating positive points from negative points or that the points are chosen uniformly at random.