The bounded blocky-matrix complexity conjecture for bounded max-norm

Let MM be a Boolean matrix, meaning a matrix with entries in {0,1}\{0,1\}. Its factorization max-norm is denoted by γ2(M)\gamma_2(M), and let bl(M)\operatorname{bl}(M) be the minimum number of blocky matrices whose ±1\pm1-linear combination is MM. The bounded blocky-matrix complexity conjecture. For every γ>0\gamma>0 there exists bγb_{\gamma} such that every Boolean matrix MM with γ2(M)γ\gamma_2(M)\leq\gamma satisfies bl(M)bγ\operatorname{bl}(M)\leq b_{\gamma}. This conjecture asks for a qualitative converse to the inequality γ2(M)bl(M)\gamma_2(M)\leq\operatorname{bl}(M) and is equivalent to Conjecture III of HHH. Its resolution status is not specified in the source.

Sources & referencesView supporting material

Primary source

István Tomon, “Factorization norms and Zarankiewicz problems”, arXiv:2502.18429 (2025).

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.