Last year, a new result appeared towards the solution of the well-known Komlos conjecture. The conjecture says that given n vectors in R^d with Euclidean norm at most one, there is always a coloring ± 1 such that the norm ℓ_1 of a signed-sum vector is constant independent of n and d. The team consisting of Nikhil Bansal, Haotian Jiang, Raghu Meki, Sahil Singli, Makrand Sinh proved this conjecture in a smoothed analysis setting in which the vectors are disturbed by the addition of a small Gaussian noise and when the number of vectors n = ω(d log d). The dependence of n on d is the best possible even in a completely random case setting. An interesting open question is what happens with more general noise models. In the final part, I will say about the progress on this issue.
You are not logged in |
