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 ... more >>>

Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing ... more >>>