ACT Seminar: Ryan O'Donnell/CMU Testing Dictators (and hardness of approximating Max-Cut-Gain) TAY 3.128
Speaker Name: R
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)
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.
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct