## Approximation Resistance from Pairwise Independent Subgroups

by Siu On Chan

#### Oded's comments

The reliance on the Unique Game Conjecture (UGC) is removed for
inapproximability results with optimal parameters for a few natural problems.
The comparison is against prior optimal quantitative results,
which used UGC, and against prior weaker quantitative results
(which used NP-hardness only, like this work).

The quantitative improvement is typically from soundness level
of $exp(sqrt k))/2^k$ to a soundness level of $2k/2^k$.
This improvement is significant for a few reasons,
the first being that the latter bound is optimal.
Other reasons refer to settings in which the actual quantities
at at a scale of $1/2^k$ (e.g., maximum independent sets
in graphs of degree $2^k$), and so the question is how much one losses
with respect to a factor of $2^k$
(at which case $poly(n)$ and $exp(sqrt k))$ are fundamentally different).

#### The original abstract

See
ECCC TR12-110

Back to
list of Oded's choices.