Paper Info
Title
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 IqR which exhibits the following property (shown for IqR 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 IqR 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(38)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.
Year
DOI
Venue
2014
10.4230/LIPIcs.STACS.2015.275
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
graph product,derandomization,low degree long code,graph coloring
Journal
30
ISSN
Citations 
PageRank 
1868-8969
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Irit Dinur1118785.67
Prahladh Harsha237132.06
Srikanth Srinivasan313221.31
Girish Varma4459.38