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.FSTTCS.2017.37
URN: urn:nbn:de:0030-drops-83956
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8395/
Go to the corresponding LIPIcs Volume Portal

Kumar, Akash ; Louis, Anand ; Tulsiani, Madhur

Finding Pseudorandom Colorings of Pseudorandom Graphs

pdf-format:
LIPIcs-FSTTCS-2017-37.pdf (0.5 MB)

Abstract

We consider the problem of recovering a planted pseudorandom 3-coloring in expanding and low threshold-rank graphs. Alon and Kahale [SICOMP 1997] gave a spectral algorithm to recover the coloring for a random graph with a planted random 3-coloring. We show that their analysis can be adapted to work when coloring is pseudorandom i.e., all color classes are of equal size and the size of the intersection of the neighborhood of a random vertex with each color class has small
variance. We also extend our results to partial colorings and low threshold-rank graphs to show the following:

* For graphs on n vertices with threshold-rank r, for which there exists a 3-coloring that is eps-pseudorandom and properly colors the induced subgraph on (1-gamma)n vertices, we show how to recover the coloring for (1 - O(gamma + eps)) n vertices in time (rn)^{O(r)}.

* For expanding graphs on n vertices, which admit a pseudorandom 3-coloring properly coloring all the vertices, we show how to recover such a coloring in polynomial time.

Our results are obtained by combining the method of Alon and Kahale, with eigenspace enumeration methods used for solving constraint satisfaction problems on low threshold-rank graphs.

BibTeX - Entry

@InProceedings{kumar_et_al:LIPIcs:2018:8395,
  author =	{Akash Kumar and Anand Louis and Madhur Tulsiani},
  title =	{{Finding Pseudorandom Colorings of Pseudorandom Graphs}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{37:1--37:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8395},
  URN =		{urn:nbn:de:0030-drops-83956},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.37},
  annote =	{Keywords: Graph Coloring, Expanders, Spectral algorithms}
}

Keywords: Graph Coloring, Expanders, Spectral algorithms
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

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