论文标题
通过正规化最小化的差异
Discrepancy Minimization via Regularization
论文作者
论文摘要
我们引入了一种基于正则化的新算法框架，以最小化差异。我们演示了改变正规化学剂如何使我们能够重新解释算法差异的几个突破性，从Spencer的定理[Spencer 1985，Bansal 2010]到Banaszczyk的界限[Banaszczyk [Banaszczyk 1998，Banasal-Dadush-Garg 2016]。使用我们的技术，我们还表明，在伪随机实例的新制度中，Beck-Fiala和Komlós的猜想是正确的。
We introduce a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to re-interpret several breakthrough works in algorithmic discrepancy, ranging from Spencer's theorem [Spencer 1985, Bansal 2010] to Banaszczyk's bounds [Banaszczyk 1998, Bansal-Dadush-Garg 2016]. Using our techniques, we also show that the Beck-Fiala and Komlós conjectures are true in a new regime of pseudorandom instances.
