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.
References
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
No solutions have been posted yet.