Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-041 | 18th March 2026 14:58

A Note on Conditional Complexity Hardness of Matrix Rigidity and Tensor Rank

RSS-Feed




TR26-041
Authors: Nikolai Chukhin
Publication: 29th March 2026 09:42
Downloads: 25
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint