1 paper · 2 filters
Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
We give an efficient algorithm to strongly refute \emph{semi-random} instances of all Boolean constraint satisfaction problems. The number of constraints required by our algorithm…