On the Komlós Conjecture
summary
Proves an O((log n)^{1/4}) bound for Komlós, improving the prior Banaszczyk O((log n)^{1/2}) rate, via a polynomial‑time constructive method that repeatedly picks SDP‑designed random walks constrained to be orthogonal to currently dangerous rows so large rows never gain discrepancy; leverages concentration and approximate independence of row increments to control medium rows and thereby resolves Beck–Fiala for k ≥ (log n)^2 while giving constructive algorithms throughout.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:02Komlós discrepancy problem
- 3:56Discrepancy bounds history
- 8:08Beck-Fiala and Komlós conjectures
- 11:21Talk plan and algorithms
- 13:51Beck-Fiala’s orthogonality trick
- 17:46BDG algorithm matching Banaszczyk
- 22:51Limitations and new ideas
- 26:01Independent discrepancy lemma
- 28:53Walks with SDPs for bounds
- 29:58Lovász Local Lemma analogy
- 31:28Q&A
related talks
35mLocal Statistics, Semidefinite Programming, and Community Detection II
01h 00mOn Approximating the Covering Radius and Finding Dense Lattice Subspaces
35mSmoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro Factorization
38mSome Easy Optimization Problems Have the Overlap-Gap Property
57mIt ain't over till it's over
45mSum of Squares SDP Relaxations on Random Tensors
32mLocal Statistics, Semidefinite Programming, and Community Detection
44mScalable Algorithmic Primitives for Data Science