Approximation Resistant Predicates From Pairwise Independence

Per Austrin, Elchanan Mossel

We study the approximability of predicates on $k$ variables from a domain $[q]$, and give a new sufficient condition for such predicates to be approximation resistant under the Uni…