Strongly Refuting Semirandom Linear Systems in Subexponential Time

Pravesh K. Kothari, Andrew D. Lin, Peter Manohar

In this paper, we consider the problem of refuting ${\mathbb{F}}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomiz…