论文标题
对科姆洛斯猜想的平滑分析
Smoothed Analysis of the Komlós Conjecture
论文作者
论文摘要
The well-known Komlós conjecture states that given $n$ vectors in $\mathbb{R}^d$ with Euclidean norm at most one, there always exists a $\pm 1$ coloring such that the $\ell_{\infty}$ norm of the signed-sum vector is a constant independent of $n$ and $d$.我们在平滑的分析设置中证明了这种猜想，在该设置中，通过添加小高斯噪声以及向量的数量$ n =ω（d \ log d）$时，向量会受到干扰。即使在完全随机的环境中，$ n $对$ d $的依赖性也是最好的。 我们的证明依赖于加权的第二钟方法，在这种方法中，我们没有考虑统一的随机着色，我们将第二矩方法应用于通过将革兰氏 - schmidt步行算法应用于合适的矢量集的颜色上的隐式分布上。主要的技术思想是使用这些着色的各种特性，包括高瑟斯，以控制第二刻。
The well-known Komlós conjecture states that given $n$ vectors in $\mathbb{R}^d$ with Euclidean norm at most one, there always exists a $\pm 1$ coloring such that the $\ell_{\infty}$ norm of the signed-sum vector is a constant independent of $n$ and $d$. We prove this conjecture in a smoothed analysis setting where the vectors are perturbed by adding a small Gaussian noise and when the number of vectors $n =ω(d\log d)$. The dependence of $n$ on $d$ is the best possible even in a completely random setting. Our proof relies on a weighted second moment method, where instead of considering uniformly randomly colorings we apply the second moment method on an implicit distribution on colorings obtained by applying the Gram-Schmidt walk algorithm to a suitable set of vectors. The main technical idea is to use various properties of these colorings, including subgaussianity, to control the second moment.
