Strong Komlós conjecture for prefix discrepancy in the Euclidean ball

About 5 years old · traced to

Let TT be a positive integer, let v1,…,vT∈B2dv_1,\ldots,v_T\in\mathbb{B}_2^d be adversarial input vectors, and let [T]={1,…,T}[T]=\{1,\ldots,T\}. A signing is a vector x∈{±1}Tx\in\{\pm1\}^T. Strong Komlós conjecture. There always exists a signing x∈{±1}Tx\in\{\pm1\}^T such that

max⁡τ∈[T]∥∑t≤τxtvt∥2=O(d).\max_{\tau\in[T]}\left\|\sum_{t\leq\tau}x_t v_t\right\|_2=O(\sqrt d).

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

Never refreshed

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.