Publication
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
STACS 2026, 2026. PDF ยท Official record
Abstract
Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform lower bounds and nonuniform lower bounds in restricted circuit models. In this paper, we show how uniform nondeterministic lower bounds can be used to construct generators of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank.
If, for some \(\varepsilon\) and \(k\), \(k\)-SAT cannot be solved in input-oblivious co-nondeterministic time \(O(2^{(1/2+\varepsilon)n})\), then there exists a monotone Boolean function family in coNP of monotone circuit size \(2^{\Omega(n/\log n)}\). This gives a win-win circuit lower bound: either \(E^{NP}\) requires superlinear series-parallel circuits or coNP requires exponentially large monotone circuits.
If MAX-3-SAT cannot be solved in co-nondeterministic time \(O(2^{(1-\varepsilon)n})\) for every \(\varepsilon>0\), then there exist small families of matrices with rigidity exceeding the best known constructions, as well as small families of three-dimensional tensors of rank \(n^{1+\Delta}\) for some \(\Delta>0\).