License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.275
URN: urn:nbn:de:0030-drops-49200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4920/
Go to the corresponding LIPIcs Volume Portal

Dinur, Irit ; Harsha, Prahladh ; Srinivasan, Srikanth ; Varma, Girish

Derandomized Graph Product Results Using the Low Degree Long Code

pdf-format:
20.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{dinur_et_al:LIPIcs:2015:4920,
  author =	{Irit Dinur and Prahladh Harsha and Srikanth Srinivasan and Girish Varma},
  title =	{{Derandomized Graph Product Results Using the Low Degree Long Code}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{275--287},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4920},
  URN =		{urn:nbn:de:0030-drops-49200},
  doi =		{10.4230/LIPIcs.STACS.2015.275},
  annote =	{Keywords: graph product, derandomization, low degree long code, graph coloring}
}

Keywords: graph product, derandomization, low degree long code, graph coloring
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI