Bansal, Nikhil ;
Jiang, Haotian ;
Meka, Raghu ;
Singla, Sahil ;
Sinha, Makrand
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
Abstract
A wellknown 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 primaldual 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 nearoptimal bounds in this setting, up to polylogarithmic factors.
BibTeX  Entry
@InProceedings{bansal_et_al:LIPIcs.ITCS.2022.13,
author = {Bansal, Nikhil and Jiang, Haotian and Meka, Raghu and Singla, Sahil and Sinha, Makrand},
title = {{Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {13:113:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15609},
URN = {urn:nbn:de:0030drops156092},
doi = {10.4230/LIPIcs.ITCS.2022.13},
annote = {Keywords: Prefix discrepancy, smoothed analysis, combinatorial vector balancing}
}
25.01.2022
Keywords: 

Prefix discrepancy, smoothed analysis, combinatorial vector balancing 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 