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.