2026-07-22T13:39:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15609 2024-03-06T10:55:44Z ddc:004 open_access

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing Bansal, Nikhil Jiang, Haotian Meka, Raghu Singla, Sahil Sinha, Makrand Prefix discrepancy smoothed analysis combinatorial vector balancing A well-known result of Banaszczyk in discrepancy theory concerns the prefix discrepancy problem (also known as the signed series problem): given a sequence of T unit vectors in ℝ^d, find ± signs for each of them such that the signed sum vector along any prefix has a small 𝓁_∞-norm? This problem is central to proving upper bounds for the Steinitz problem, and the popular Komlós problem is a special case where one is only concerned with the final signed sum vector instead of all prefixes. Banaszczyk gave an O(√{log d+ log T}) bound for the prefix discrepancy problem. We investigate the tightness of Banaszczyk’s bound and consider natural generalizations of prefix discrepancy: - We first consider a smoothed analysis setting, where a small amount of additive noise perturbs the input vectors. We show an exponential improvement in T compared to Banaszczyk’s bound. Using a primal-dual approach and a careful chaining argument, we show that one can achieve a bound of O(√{log d+ log log T}) with high probability in the smoothed setting. Moreover, this smoothed analysis bound is the best possible without further improvement on Banaszczyk’s bound in the worst case. - We also introduce a generalization of the prefix discrepancy problem to arbitrary DAGs. Here, vertices correspond to unit vectors, and the discrepancy constraints correspond to paths on a DAG on T vertices - prefix discrepancy is precisely captured when the DAG is a simple path. We show that an analog of Banaszczyk’s O(√{log d+ log T}) bound continues to hold in this setting for adversarially given unit vectors and that the √{log T} factor is unavoidable for DAGs. We also show that unlike for prefix discrepancy, the dependence on T cannot be improved significantly in the smoothed case for DAGs. - We conclude by exploring a more general notion of vector balancing, which we call combinatorial vector balancing. In this problem, the discrepancy constraints are generalized from paths of a DAG to an arbitrary set system. We obtain near-optimal bounds in this setting, up to poly-logarithmic factors. 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 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.13 urn:nbn:de:0030-drops-156092 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.13 eng https://creativecommons.org/licenses/by/4.0/legalcode