2026-08-10T11:37:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16355 2024-03-06T10:57:15Z ddc:004 open_access

Smoothed Analysis of the Komlós Conjecture Bansal, Nikhil Jiang, Haotian Meka, Raghu Singla, Sahil Sinha, Makrand Komlós conjecture smoothed analysis weighted second moment method subgaussian coloring The well-known Komló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 = ω(d log 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Bansal and Haotian Jiang and Raghu Meka and Sahil Singla and Makrand Sinha 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.14 urn:nbn:de:0030-drops-163556 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode