论文标题
通过低维嵌入方式舍入
Rounding via Low Dimensional Embeddings
论文作者
论文摘要
常规图$ g =（v，e）$是$（\ varepsilon，γ）$小型膨胀机，如果对于任何最多$ \ varepsilon $，至少是$ \ varepsilon $，至少$γ$的边缘的$γ$。在本文中，我们为小型扩展器的几种已知复杂性理论结果提供了统一的方法。特别是，我们表明： 1. Max-Cut: we show that if a regular graph $G = (V,E)$ is an $(\varepsilon,γ)$ small-set expander that contains a cut of fractional size at least $1-δ$, then one can find in $G$ a cut of fractional size at least $1-O\left(\fracδ{\varepsilonγ^6}\right)$ in polynomial time. 2。改进的光谱分区，Cheeger的不平等和对小型扩展器的平行重复定理。这些结果中的每一个的一般形式涉及某些舍入过程所带来的方形 - 根损失，我们展示了如何在小型集合扩张器上避免这种情况。 我们的主要思想是将高维矢量解决方案投射到低维空间中，同时大致维护$ \ ell_2^2 $距离，然后使用低维几何形状执行预处理步骤，并且属性$ \ ell_2^2 $ destances of the of the。这种预处理利用图形的小型扩展特性将矢量值的解变为具有其他结构特性的不同矢量值的解决方案，从而导致更有效的积分解决方案方案。
A regular graph $G = (V,E)$ is an $(\varepsilon,γ)$ small-set expander if for any set of vertices of fractional size at most $\varepsilon$, at least $γ$ of the edges that are adjacent to it go outside. In this paper, we give a unified approach to several known complexity-theoretic results on small-set expanders. In particular, we show: 1. Max-Cut: we show that if a regular graph $G = (V,E)$ is an $(\varepsilon,γ)$ small-set expander that contains a cut of fractional size at least $1-δ$, then one can find in $G$ a cut of fractional size at least $1-O\left(\fracδ{\varepsilonγ^6}\right)$ in polynomial time. 2. Improved spectral partitioning, Cheeger's inequality and the parallel repetition theorem over small-set expanders. The general form of each one of these results involves square-root loss that comes from certain rounding procedure, and we show how this can be avoided over small set expanders. Our main idea is to project a high dimensional vector solution into a low-dimensional space while roughly maintaining $\ell_2^2$ distances, and then perform a pre-processing step using low-dimensional geometry and the properties of $\ell_2^2$ distances over it. This pre-processing leverages the small-set expansion property of the graph to transform a vector valued solution to a different vector valued solution with additional structural properties, which give rise to more efficient integral-solution rounding schemes.
