10/28/2005

3

•Often, using
unique-games-conjecture (Khot 2002), after constructing the
outer-verifier,

•(Very) roughly speaking the hardness of approximation factor is given by c/s where

•c = limd ! 0 supn,f {Sh(f) : I(f) · d, E[f] = 0}

•s = supn,f E[Sh(f) : E[f] = 0}

for an
appropriate value of h

(sometimes need
variant of Sh)

•s is typically easy to analyze –

it is maximized by a
dictator.

•It is harder to find c.