2026-07-22T12:15:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4920 2024-03-06T10:35:33Z ddc:004 open_access

Derandomized Graph Product Results Using the Low Degree Long Code Dinur, Irit Harsha, Prahladh Srinivasan, Srikanth Varma, Girish graph product derandomization low degree long code graph coloring 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Irit Dinur and Prahladh Harsha and Srikanth Srinivasan and Girish Varma 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.275 urn:nbn:de:0030-drops-49200 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.275 eng https://creativecommons.org/licenses/by/3.0/legalcode