Derandomized Graph Product Results Using the Low Degree Long Code

Abstract

In this paper, we address the question of whether the recent derandomization results obtained by the use of the low-degree long code can be extended to other product settings. We consider two settings: (1) the graph product results of Alon, Dinur, Friedgut and Sudakov [GAFA, 2004] and (2) the "majority is stablest" type of result obtained by Dinur, Mossel and Regev [SICOMP, 2009] and Dinur and Shinkar [In Proc. APPROX, 2010] while studying the hardness of approximate graph coloring.

In our first result, we show that there exists a considerably smaller
subgraph of K_3^{\otimes R} which exhibits the following property
(shown for K_3^{\otimes R} by Alon et al.): independent sets close in
size to the maximum independent set are well approximated by dictators.

The "majority is stablest" type of result of Dinur et al. and Dinur
and Shinkar shows that if there exist two sets of vertices A and B
in K_3^{\otimes R} with very few edges with one endpoint in A and
another in B, then it must be the case that the two sets A and B
share a single influential coordinate. In our second result, we show
that a similar "majority is stablest" statement holds good for a
considerably smaller subgraph of K_3^{\otimes R}. Furthermore using
this result, we give a more efficient reduction from Unique Games
to the graph coloring problem, leading to improved hardness  of
approximation results for coloring.