Gaussian discrepancy: A probabilistic relaxation of vector balancing
Gaussian discrepancy: A probabilistic relaxation of vector balancing
复制标题
高斯差异：矢量平衡的概率松弛
DOI：
10.1016/j.dam.2022.08.007
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Turner, Paxton
中科院分区：
文献类型：
--
作者：
Chewi, Sinho;Gerber, Patrik;Rigollet, Philippe;Turner, Paxton
我们引入了一种新颖的组合差异松弛方法，称为高斯差异，其中二进制符号被相关的标准高斯随机变量取代。这种松弛有效地将布尔超立方体上的优化问题重新表述为相关矩阵空间上的优化问题。我们证明，高斯差异是比之前研究的矢量和球面差异问题更严格的松弛，并且我们构建了一种快速在线算法，该算法实现了高斯差异的 Banaszczyk 界限版本。这项工作还提出了新的问题，例如高斯差异的科姆洛斯猜想，这可能有助于揭示经典差异问题。
We introduce a novel relaxation of combinatorial discrepancy calledGaussian discrepancy, whereby binary signings are replaced with correlated standard Gaussian random variables. This relaxation effectively reformulates an optimization problem over the Boolean hypercube into one over the space of correlation matrices. We show that Gaussian discrepancy is a tighter relaxation than the previously studied vector and spherical discrepancy problems, and we construct a fast online algorithm that achieves a version of the Banaszczyk bound for Gaussian discrepancy. This work also raises new questions such as the Komlós conjecture for Gaussian discrepancy, which may shed light on classical discrepancy problems.