"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) = xi. 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 uses tools from Fourier analysis. The lower bound proof uses a semidefinite programming algorithm of Zwick.
Joint work with Yi Wu of Carnegie Mellon University.