2026-07-25T01:47:07Z https://drops.dagstuhl.de/oai

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

Gap Amplification for Small-Set Expansion via Random Walks Raghavendra, Prasad Schramm, Tselil Gap amplification Small-Set Expansion random walks graph products Unique Games 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prasad Raghavendra and Tselil Schramm 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.381 urn:nbn:de:0030-drops-47108 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.381 eng https://creativecommons.org/licenses/by/3.0/legalcode