标题： 通过仿射谱独立性解耦：超越Banasczyk的Beck-Fiala和Komlós界限 显示英文标题

标题： Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk

摘要： 贝克-菲拉猜想[离散应用数学，1981]断言，任何具有$n$个元素且度数为$k$的集合系统具有组合差异$O(\sqrt{k})$。一个重要的推广是科姆洛斯猜想，它指出任何具有单位长度列的$m \times n$矩阵具有差异$O(1)$。在本工作中，我们解决了$k \geq \log^2 n$的贝克-菲拉猜想。 We also give an $\widetilde{O}(\sqrt{k} + \sqrt{\log n})$ bound for $k \leq \log^2 n$, where $\widetilde{O}(\cdot)$ hides $\mathsf{poly}(\log \log n)$ factors. These bounds improve upon the $O(\sqrt{k \log n})$ bound due to Banaszczyk [Random Struct. Algor., 1998]. For the Komlos problem, we give an $\widetilde{O}(\log^{1/4} n)$ bound, improving upon the previous $O(\sqrt{\log n})$ bound [Random Struct. Algor., 1998]. All of our results also admit efficient polynomial-time algorithms. To obtain these results, we consider a new notion of affine spectral-independence in designing random walks. In particular, our algorithms obtain the desired colorings via a discrete Brownian motion, guided by a semidefinite program (SDP). Besides standard constraints used in prior works, we add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancy across different rows, and allow us to better control how many rows accumulate large discrepancy at any point during the process. This technique of ``decoupling via affine spectral-independence'' is quite general and may be of independent interest. 显示英文摘要

摘要： The Beck-Fiala Conjecture [Discrete Appl. Math, 1981] asserts that any set system of $n$ elements with degree $k$ has combinatorial discrepancy $O(\sqrt{k})$. A substantial generalization is the Koml\'os Conjecture, which states that any $m \times n$ matrix with unit length columns has discrepancy $O(1)$. In this work, we resolve the Beck-Fiala Conjecture for $k \geq \log^2 n$. We also give an $\widetilde{O}(\sqrt{k} + \sqrt{\log n})$ bound for $k \leq \log^2 n$, where $\widetilde{O}(\cdot)$ hides $\mathsf{poly}(\log \log n)$ factors. These bounds improve upon the $O(\sqrt{k \log n})$ bound due to Banaszczyk [Random Struct. Algor., 1998]. For the Komlos problem, we give an $\widetilde{O}(\log^{1/4} n)$ bound, improving upon the previous $O(\sqrt{\log n})$ bound [Random Struct. Algor., 1998]. All of our results also admit efficient polynomial-time algorithms. To obtain these results, we consider a new notion of affine spectral-independence in designing random walks. In particular, our algorithms obtain the desired colorings via a discrete Brownian motion, guided by a semidefinite program (SDP). Besides standard constraints used in prior works, we add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancy across different rows, and allow us to better control how many rows accumulate large discrepancy at any point during the process. This technique of ``decoupling via affine spectral-independence'' is quite general and may be of independent interest.