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.
