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

Determining the randomized (or distributional) communication complexity of disjointness is a central problem in communication complexity, having roots in the foundational work of Babai, Frankl, and Simon in the 1980s and culminating in the famous works of Kalyanasundaram-Schnitger and Razborov in 1992. However, the question of obtaining tight bounds for ... more >>>

Proving lower bounds against depth-$2$ linear threshold circuits (a.k.a. $THR \circ THR$) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for $THR \circ THR$ only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and ... more >>>