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.