Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank

Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin +1

Proving complexity lower bounds remains a challenging task: we only know how to prove conditional uniform lower bounds and nonuniform lower bounds in restricted circuit models. Wil…