@inproceedings{be95748a434a40b49c5766184f094ceb,
title = "Smoothed Analysis of the Koml{\'o}s Conjecture",
abstract = "The well-known Koml{\'o}s conjecture states that given n vectors in ℝd with Euclidean norm at most one, there always exists a ±1 coloring such that the ℓ∞ norm of the signed-sum vector is a constant independent of n and d. We prove this conjecture in a smoothed analysis setting where the vectors are perturbed by adding a small Gaussian noise and when the number of vectors n = ω(dlog d). The dependence of n on d is the best possible even in a completely random setting. Our proof relies on a weighted second moment method, where instead of considering uniformly randomly colorings we apply the second moment method on an implicit distribution on colorings obtained by applying the Gram-Schmidt walk algorithm to a suitable set of vectors. The main technical idea is to use various properties of these colorings, including subgaussianity, to control the second moment.",
keywords = "Koml{\'o}s conjecture, smoothed analysis, subgaussian coloring, weighted second moment method",
author = "Nikhil Bansal and Haotian Jiang and Raghu Meka and Sahil Singla and Makrand Sinha",
note = "Funding Nikhil Bansal: Supported in part by the NWO VICI grant 639.023.812. Haotian Jiang: Supported by NSF awards CCF-1749609, DMS-1839116, DMS-2023166, CCF-2105772. Makrand Sinha: Supported by a Simons-Berkeley postdoctoral fellowship.; 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 ; Conference date: 04-07-2022 Through 08-07-2022",
year = "2022",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2022.14",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Mikolaj Bojanczyk and Emanuela Merelli and Woodruff, {David P.}",
booktitle = "49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022",
address = "Germany",
}