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 Unique Games Conjecture. Specifically, we show that a predicate $P$ is approximation resistant if there exists a balanced pairwise independent distribution over ... more >>>

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

We study the approximate-coloring(q,Q) problem: Given a graph G, decide whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional hardness for this problem for any constant 3\le q < Q. For q \ge 4, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For q=3, we base our hardness ... more >>>

Cryan and Miltersen recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator such that every bit of the output depends on a constant number k of bits of the seed. They show that for k=3 there is always a distinguisher; ... more >>>