Discrepancy Minimization via Regularization

on YouTube ↗57m

" summary

Introduces a concrete algorithmic framework that uses regularization to smooth the max norm, runs a continuous Newton-style update on fractional colorings, and trades smoothness error vs curvature by choosing the square-root regularizer instead of entropy. Proves a constructive Spencer bound with constant 3.67·√n, reinterprets results up to Banaszczyk, and shows Komlós and Beck–Fiala hold for a new pseudorandom regime (random rotations give constant discrepancy), at the cost of non‑fast runtime.

AI-written summary · about

" chapters (14)

1. 0:00Discrepancy minimization intro
2. 1:08Spencer's classical problem
3. 6:11Random coloring limits
4. 8:00Why new algorithms matter
5. 13:22Beck-Fiala & Komlós overview
6. 14:04Newton's method for Spencer
7. 19:55Regularization for max smoothing
8. 24:54Regularization trade-offs
9. 31:09Controlling discrepancy growth
10. 36:15Improved Spencer's constant proof
11. 41:53Extending to Komlós conjecture
12. 43:20Obstacles in Spencer approach
13. 48:10Pseudorandomness in Komlós
14. 51:24Results & open questions