Komlós's conjecture for vector balancing

Let ARm×nA\in\mathbb{R}^{m\times n} be a matrix whose columns have Euclidean norm at most 11, and let

disc(A):=minσ{±1}nAσ.\operatorname{disc}(A):=\min_{\sigma\in\{\pm1\}^n}\|A\sigma\|_\infty.

Komlós's conjecture. There exists a constant K>0K>0 such that, for every such matrix AA,

disc(A)K.\operatorname{disc}(A)\leq K.

This is a major open problem in discrepancy theory. Banaszczyk's bound gives disc(A)=O(log(min{m,n}))\operatorname{disc}(A)=O(\sqrt{\log(\min\{m,n\})}), and the conjecture contains the Beck–Fiala conjecture as a special case.

Sources & referencesView supporting material

Primary source

Sinho Chewi, Patrik Gerber, Philippe Rigollet and Paxton Turner, “Gaussian discrepancy: a probabilistic relaxation of vector balancing”, arXiv:2109.08280 (2022).

Additional references

2 papers in this index state this conjecture (2018–2021). The statement above is taken from the most recent of them; the others are arXiv:1807.04318.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.