•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.