Komlós's conjecture for vector balancing
Komlós's conjecture for vector balancing
Let be a matrix whose columns have Euclidean norm at most , and let
Komlós's conjecture. There exists a constant such that, for every such matrix ,
This is a major open problem in discrepancy theory. Banaszczyk's bound gives , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.