The bounded row and column sum discrepancy conjecture

About 13 years old · traced to

Let VV be an n×mn \times m real matrix with ∣Vi,j∣≤1|V_{i,j}| \leq 1, ∥vi∥1≤R\|v^i\|_1 \leq R, and ∥vj∥1≤Δ\|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

∥Vy∥∞≤O(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.

References

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.