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

Let TT be a positive integer, let v1,,vTB2dv_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τxtvt2=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.

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

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.