The bounded blocky-matrix complexity conjecture for bounded max-norm
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.
Sources & referencesView supporting material
Primary source
István Tomon, “Factorization norms and Zarankiewicz problems”, arXiv:2502.18429 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.