4
[2211.05509] Discrepancy Minimization via Regularization
source link: https://arxiv.org/abs/2211.05509
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 10 Nov 2022]
Discrepancy Minimization via Regularization
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.
| Comments: | SODA 2023 |
| Subjects: | Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2211.05509 [cs.DS] |
| (or arXiv:2211.05509v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2211.05509 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK