The optimal expected online discrepancy conjecture for sparse random vectors

Let $\mu_d$ be the distribution on $\{0,1\}^n$ used in the paper's sparse matrix model, and let $\mathrm{ondisc}(\mu_d,n)$ denote the optimal expected online discrepancy over $n$ arrivals. Here $\mathrm{ondisc}(\mu_d,n)$ is the infimum, over online signing algorithms, of the expected maximum infinity norm of the signed partial sums.

Optimal expected online discrepancy conjecture. For all $2\leq d\leq n/2$,

$$\mathrm{ondisc}(\mu_d,n)=\Theta\bigl(\max(\sqrt{d},\log\log n)\bigr).$$

The paper proves the order $\Theta(\log\log n)$ in a smaller range of $d$ and identifies the regime $d=\Omega((\log\log n)^2)$ as open. The conjecture proposes the optimal order throughout the full stated range.