The bounded row and column sum discrepancy conjecture

Let VV be an n×mn \times m real matrix with Vi,j1|V_{i,j}| \leq 1, vi1R\|v^i\|_1 \leq R, and vj1Δ\|v_j\|_1 \leq \Delta for all i[n]i \in [n] and j[m]j \in [m]. Assume RΔR \geq \Delta. The bounded row and column sum discrepancy conjecture. There exists y{1,+1}my \in \{-1,+1\}^m such that

VyO(R).\|Vy\|_\infty \leq O(\sqrt{R}).

This conjecture asks whether the logarithmic factor in the paper’s discrepancy bounds can be removed. The source does not provide evidence that the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Nicholas J. A. Harvey, “A note on the discrepancy of matrices with bounded row and column sums”, arXiv:1307.2159 (2013).

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.