CSAIL Event Calendar: Previous Series

3-Query Dictator Testing

Speaker: Ryan O'Donnell , CMU
Date: December 4 2007
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Madhu Sudan, MIT, CSAIL

"Dictator Testing" is a Property Testing problem with direct applications to PCP constructions and hardness of approximation. The task is to test if an unknown function f : {0,1}^n -> {0,1} is a "Dictator" -- i.e., one of the n functions f(x) = x_i. However the number of queries allowed is even smaller than usual: only 2 or 3. To compensate, one only needs to reject "quasirandom" functions with high probability.

In this talk we consider the problem of Dictator Testing with 3 queries and perfect completeness. We show that the lowest possible soundness achievable is 5/8. The upper bound proof requires a new generalization of the Bonami-Beckner inequality. The lower bound proof uses a semidefinite programming algorithm of Zwick.

Joint work with Yi Wu of Carnegie Mellon University.

See other events that are part of Theory Colloquium Fall 2007

See other events happening in December 2007