[Lowerbounds, Upperbounds]

Friday, September 22nd, 3:30pm WEH 7220

Title: Agnostically Learning Halfspaces
Speaker: Dr. Adam Klivans, University of Texas at Austin

Abstract: We give the first algorithm that efficiently learns halfspaces (under distributional assumptions) in the notoriously difficult agnostic framework of Kearns, Schapire, and Sellie. In this model, a learner is given arbitrarily labeled examples from a fixed distribution and must output a hypothesis competitive with the optimal halfspace hypothesis.

Our algorithm constructs a hypothesis whose error rate on future examples is within an additive ε of the optimal halfspace in time poly(n) for any constant ε > 0 under the uniform distribution over {0,1}^n or the unit sphere in R^n, as well as under any log-concave distribution over R^n. It also agnostically learns Boolean disjunctions in time 2^Õ(√n) with respect to any distribution. The new algorithm, essentially L_1 polynomial regression, is a noise-tolerant arbitrary-distribution generalization of the “low-degree” Fourier algorithm of Linial, Mansour, and Nisan. Our Fourier-type algorithm over the unit sphere makes use of approximation properties of various classes of orthogonal polynomials.

Joint work with A. Kalai, Y. Mansour, and R. Servedio.

SPEAKER: Ryan O’Donnell.
TIME: Wednesday 12-1pm, September 20, 2006.
PLACE: NSH 1507
TITLE: Testing Dictators (and the hardness of approximating Max-Cut-Gain)

ABSTRACT:

“Dictator functions” are functions f : {0,1}^n -> {0,1} of the form f(x) = x_i. Given an unknown function f, a “dictator test” involves querying f(x) at an extremely small number of random points x and performing a test on the results. The test should pass with significantly higher probability when f is a dictator function than when f is far from being a dictator function.

The main interest in highly query-efficient dictator tests is they can usually be transformed into hardness-of-approximation results for basic algorithmic problems like Max-3LIN, Min-Vertex-Cover, etc. (using PCP technology).

In this talk we will review some known 2-query and 3-query dictator tests. We will then describe a new 2-query dictator test and show how it leads to an optimal new hardness-of-approximation result for the Max-Cut-Gain problem.

This includes joint work with Subhash Khot of Georgia Tech.