Komlós's conjecture for vector balancing

About 8 years old · traced to

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

disc⁡(A):=min⁡σ∈{±1}n∥Aσ∥∞.\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.

References

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.