Type of Talk: ACT Seminar

Speaker Name: R

yan O''Donnell

Speaker Affiliation: CMU

Date: Tuesday Nove

mber 14 2006

Start Time: 1:00 p.m.

Coffee: 12:45 p.m.
<

br>Location: TAY 3.128

Host: Adam Klivans

Talk Title: Test

ing Dictators (and hardness of approximating Max-Cut-Gain)

Talk Abst

ract:
Dictator functions are functions f : %7B0 1%7D%5En -> %7B0 1%7D

of the form f(x) = x_i. Given an unknown function f a dictator test invol

ves querying f(x) at an extremely small number of random points x and perfo

rming a test on the results. The test should pass with significantly highe

r 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 te

sts is that 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-q

uery and 3-query dictator tests. We will then describe a new 2-query dicta

tor 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 S

ubhash Khot of Georgia Tech.