Reductions between Expansion Problems
Reductions between Expansion Problems
复制标题
扩展问题之间的约简
DOI：
10.1109/ccc.2012.43
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Madhur Tulsiani
中科院分区：
文献类型：
--
作者：
P. Raghavendra;David Steurer;Madhur Tulsiani
小集合扩张假设（Raghavendra，Steurer，STOC 2010）是一个关于图中小集合边扩张近似问题的自然困难假设。这个困难假设与唯一游戏猜想（Khot，STOC 2002）密切相关。特别是，小集合扩展假设暗示了唯一博弈猜想（Raghavendra，Steurer，STOC 2010）。我们的主要结果是，小集扩展假设实际上是等价的唯一游戏猜想的一个变种。更确切地说，该假设等价于仅限于小集合扩张条件相当温和的情况下的唯一博弈猜想。此外，我们还获得了平衡分离器和最小线性排列问题近似结果的第一个强硬度。以前，即使假设唯一博弈猜想，也没有这样的难度。这些结果不仅建立了小集合膨胀假设作为一个自然的统一的假设，这意味着唯一的游戏猜想，其所有的后果，此外，硬度结果的其他问题，如平衡分离器和最小线性排列，但我们的研究结果也表明，小集合膨胀假设的问题在于组合的唯一游戏猜想的心脏。关键的技术成分是一种新的方式，利用从小集合扩展假设中获得的独特游戏实例的结构（Raghavendra，Steurer，2010）。这种额外的结构允许我们以一种基本上破坏其本地小工具性质的方式修改标准缩减。使用这种修改，我们可以讨论缩减产生的图中的扩展，而不依赖于底层Unique Games实例的扩展属性（这对于本地小工具缩减是不可能的）。
The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique Games Conjecture (Raghavendra, Steurer, STOC 2010). Our main result is that the Small-Set Expansion Hypothesis is in fact equivalent to a variant of the Unique Games Conjecture. More precisely, the hypothesis is equivalent to the Unique Games Conjecture restricted to instance with a fairly mild condition on the expansion of small sets. Alongside, we obtain the first strong hardness of approximation results for the Balanced Separator and Minimum Linear Arrangement problems. Before, no such hardness was known for these problems even assuming the Unique Games Conjecture. These results not only establish the Small-Set Expansion Hypothesis as a natural unifying hypothesis that implies the Unique Games Conjecture, all its consequences and, in addition, hardness results for other problems like Balanced Separator and Minimum Linear Arrangement, but our results also show that the Small-Set Expansion Hypothesis problem lies at the combinatorial heart of the Unique Games Conjecture. The key technical ingredient is a new way of exploiting the structure of the Unique Games instances obtained from the Small-Set Expansion Hypothesis via (Raghavendra, Steurer, 2010). This additional structure allows us to modify standard reductions in a way that essentially destroys their local-gadget nature. Using this modification, we can argue about the expansion in the graphs produced by the reduction without relying on expansion properties of the underlying Unique Games instance (which would be impossible for a local-gadget reduction).