{"id":191120,"date":"2014-07-16T00:00:00","date_gmt":"2014-07-16T10:41:12","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/gap-amplification-for-small-set-expansion-via-random-walks\/"},"modified":"2016-07-15T15:17:59","modified_gmt":"2016-07-15T22:17:59","slug":"gap-amplification-for-small-set-expansion-via-random-walks","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/gap-amplification-for-small-set-expansion-via-random-walks\/","title":{"rendered":"Gap Amplification for Small-Set Expansion via Random Walks"},"content":{"rendered":"<div class=\"asset-content\">\n<p>The Small-Set Expansion problem is the problem of finding sets in a graph that meet specific size and expansion bounds; this problem has received a lot of attention in the past couple of years due to its close relationship with the Unique Games problem. In this talk, I will show how to achieve gap amplification for the Small-Set Expansion problem. Specifically, I will show that an instance of the Small-Set Expansion Problem with completeness \u03b5 and soundness 1\/2 is at least as difficult as Small-Set Expansion with completeness \u03f5 and soundness f(\u03b5) for any function f(\u03b5) which grows faster than \u03b5^(1\/2). This amplification is achieved via random walks \u2013 the gadget is the graph with adjacency matrix corresponding to a random walk on the original graph. An interesting feature of the reduction is that unlike gap amplification via parallel repetition (such as the gap amplification for Unique Games), the size of the instances (number of vertices) produced by the reduction remains the same.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Small-Set Expansion problem is the problem of finding sets in a graph that meet specific size and expansion bounds; this problem has received a lot of attention in the past couple of years due to its close relationship with the Unique Games problem. In this talk, I will show how to achieve gap amplification [&hellip;]<\/p>\n","protected":false},"featured_media":198472,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[206954],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-191120","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-video-type-microsoft-research-talks","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/kcZOgDOZ060","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/191120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/191120\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/198472"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=191120"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=191120"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=191120"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=191120"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=191120"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=191120"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=191120"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=191120"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=191120"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=191120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}