Strong Komlós conjecture for prefix discrepancy in the Euclidean ball
Strong Komlós conjecture for prefix discrepancy in the Euclidean ball
Let be a positive integer, let be adversarial input vectors, and let . A signing is a vector . Strong Komlós conjecture. There always exists a signing such that
This asks for a dimension-dependent prefix-discrepancy bound for adversarial vectors in the Euclidean unit ball. The paper notes that related prefix-discrepancy questions have been posed for other norms; the status evidence identifies the Beck–Fiala version as another related open problem, and this conjecture remains open.
Sources & referencesView supporting material
Primary source
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla and Makrand Sinha, “Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing”, arXiv:2111.07049 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.