The bounded blocky-matrix complexity conjecture for bounded max-norm
Let be a Boolean matrix, meaning a matrix with entries in . Its factorization max-norm is denoted by , and let be the minimum number of blocky matrices whose -linear combination is . The bounded blocky-matrix complexity conjecture. For every there exists such that every Boolean matrix with satisfies . This conjecture asks for a qualitative converse to the inequality and is equivalent to Conjecture III of HHH. Its resolution status is not specified in the source.
References
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.