TR26-041 | A Note on Conditional Complexity Hardness of Matrix Rigidity and Tensor Rank | Nikolai Chukhin

Recently, together with Kulikov, Mihajlin, and Smirnova (STACS 2026), we gave conditional constructions of functions with large monotone circuit complexity, matrices with high rigidity, and $3$-dimensional tensors of strongly superlinear rank. In this note, I strengthen the rigidity construction under the same assumption and, as a direct consequence, immediately obtain a slightly improved trade-off theorem for tensor rank.