Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Sem. RP


Smoothed Analysis of the Komlos Conjecture

Prelegent: Witold Bednorz

2023-03-30 12:15

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.