Tests of deviation from dictatorship
Speaker:
Elchanan Mossel, University of California Berkeley
Date and Time:
Saturday, August 13, 2011 - 9:30am to 10:30am
Abstract:
I will give an overview of what we know (and don't know) about ("long code") tests separating dictatorships from functions far from dictatorships. Such tests play a role in proving hardness of approximation for constraint satisfaction problems.
