Publication
A Note on Conditional Complexity Hardness of Matrix Rigidity and Tensor Rank
ECCC TR26-041, 2026. PDF ยท Official record
Abstract
Recently, together with Kulikov, Mihajlin, and Smirnova, we gave conditional constructions of functions with large monotone circuit complexity, matrices with high rigidity, and three-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.