TY - GEN
T1 - Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
AU - Bansal, Nikhil
AU - Jiang, Haotian
AU - Meka, Raghu
AU - Singla, Sahil
AU - Sinha, Makrand
N1 - Funding Information:
Funding Nikhil Bansal: Supported in part by the NWO VICI grant 639.023.812. The work was done when the author was at CWI, Amsterdam. Haotian Jiang: Supported in part by the National Science Foundation, Grant Number CCF-1749609, CCF-1740551, DMS-1839116.
Funding Information:
Nikhil Bansal: Supported in part by the NWO VICI grant 639.023.812. The work was done when the author was at CWI, Amsterdam. Haotian Jiang: Supported in part by the National Science Foundation, Grant Number CCF-1749609, CCF-1740551, DMS-1839116. Raghu Meka: Supported by NSF Grant CCF-1553605. Sahil Singla: The work was partly done when the author was at Princeton University. Makrand Sinha: Work done while at CWI Amsterdam and supported by the NWO VICI grant 639.023.812. The authors would like to thank the anonymous reviewers of ITCS 2022 for helpful comments.
Funding Information:
Raghu Meka: Supported by NSF Grant CCF-1553605. Sahil Singla: The work was partly done when the author was at Princeton University. Makrand Sinha: Work done while at CWI Amsterdam and supported by the NWO VICI grant 639.023.812.
Publisher Copyright:
© Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha; licensed under Creative Commons License CC-BY 4.0
PY - 2022/1/1
Y1 - 2022/1/1
N2 - 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 Rd, 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 + loglog 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.
AB - 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 Rd, 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 + loglog 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.
KW - Combinatorial vector balancing
KW - Prefix discrepancy
KW - Smoothed analysis
UR - http://www.scopus.com/inward/record.url?scp=85124023648&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85124023648&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2022.13
DO - 10.4230/LIPIcs.ITCS.2022.13
M3 - Conference contribution
AN - SCOPUS:85124023648
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
A2 - Braverman, Mark
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Y2 - 31 January 2022 through 3 February 2022
ER -