Determine whether there exist universal constants C,c>0 and a polynomial-time online signing algorithm such that, for every dimension n≥ 1 and every finite horizon T, when v_1,…,v_T are independent samples from N(0,I_n), the algorithm chooses each x_t∈pm1 upon seeing v_t and satisfies P!(|∑_t=1^Tx_t v_t|_∞≤ C√n)≥ 1-exp(-c√n). The algorithm should operate online and its guarantee should be independent of T.

Online discrepancy conjecture

Gamarnik et al. (2022) conjectured an efficient online signing strategy achieving dimension-scale discrepancy for Gaussian inputs, with the analogous question for broader input distributions.

Known results

Bansal and Spencer (2020) obtained an efficient dimension-scale bound for Rademacher inputs.
Gamarnik et al. (2023) established geometric lower bounds showing that relevant online algorithms generally cannot beat a constant multiple of $\sqrt{n}$ , supporting the conjectured scale.
Vafa and Vaikuntanathan (2025) are cited for a conditional computational limitation against polynomial-factor improvement when $T$ is sufficiently larger than $n$ .

August 2026 claimed advance

Nicola Wengiel’s version- $1$ manuscript claims a polynomial-time algorithm for independent sub-Gaussian coordinates with terminal discrepancy $O(\sigma^8\sqrt{n})$ , uniformly over every finite horizon $T$ ; for Gaussian inputs this reaches the conjectured $O(\sqrt{n})$ scale, up to a parameter-dependent constant. It also claims a masked-coordinate bound of $O(\sigma^8\sqrt{k})$ . The claim is unrefereed and no independent verification or objection was found.

Current status (as of August 2026): The Gaussian $O(\sqrt{n})$ target is claimed by an unrefereed manuscript, while the conjecture’s full generality and the claim’s correctness remain open.

Online discrepancy conjecture

Progress summary

Primary source

Additional references

Solutions 0