License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.13
URN: urn:nbn:de:0030-drops-156092
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15609/
Bansal, Nikhil ;
Jiang, Haotian ;
Meka, Raghu ;
Singla, Sahil ;
Sinha, Makrand
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
Abstract
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.
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:1--13:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15609},
URN = {urn:nbn:de:0030-drops-156092},
doi = {10.4230/LIPIcs.ITCS.2022.13},
annote = {Keywords: Prefix discrepancy, smoothed analysis, combinatorial vector balancing}
}
|
Keywords: |
|
Prefix discrepancy, smoothed analysis, combinatorial vector balancing |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
