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.APPROX-RANDOM.2014.381
URN: urn:nbn:de:0030-drops-47108
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4710/
Go to the corresponding LIPIcs Volume Portal

Raghavendra, Prasad ; Schramm, Tselil

Gap Amplification for Small-Set Expansion via Random Walks

pdf-format:
27.pdf (0.4 MB)

Abstract

In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness epsilon and soundness 1/2 is at least as difficult as Small-Set Expansion with completeness epsilon and soundness f(epsilon), for any function f(epsilon) which grows faster than (epsilon)^(1/2). We achieve this amplification via random walks--the output graph corresponds to taking random walks on the original graph. An interesting feature of our reduction is that unlike gap amplification via parallel repetition, the size of the instances (number of vertices) produced by the reduction remains the same.

BibTeX - Entry

@InProceedings{raghavendra_et_al:LIPIcs:2014:4710,
  author =	{Prasad Raghavendra and Tselil Schramm},
  title =	{{Gap Amplification for Small-Set Expansion via Random Walks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{381--391},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4710},
  URN =		{urn:nbn:de:0030-drops-47108},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.381},
  annote =	{Keywords: Gap amplification, Small-Set Expansion, random walks, graph products, Unique Games}
}

Keywords: Gap amplification, Small-Set Expansion, random walks, graph products, Unique Games
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

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