We give an efficient algorithm to strongly refute *semi-random* instances of all Boolean constraint satisfaction problems. The number of constraints required by our algorithm matches (up to polylogarithmic factors) the best-known bounds for efficient refutation of fully random instances. Our main technical contribution is an algorithm to strongly refute semi-random instances of the Boolean \(k\)-XOR problem on \(n\) variables that have \(\tilde O(n^{k/2})\) constraints. (In a semi-random \(k\)-XOR instance, the equations can be arbitrary and only the right-hand sides are random.)

One of our key insights is to identify a simple combinatorial property of random XOR instances that makes spectral refutation work. Our approach involves taking an instance that does not satisfy this property (i.e., is *not* pseudorandom) and reducing it to a partitioned collection of 2-XOR instances. We analyze these subinstances using a carefully chosen quadratic form as a proxy, which in turn is bounded via a combination of spectral methods and semidefinite programming. The analysis of our spectral bounds relies only on an off-the-shelf matrix Bernstein inequality. Even for the purely random case, this leads to a shorter proof compared to the ones in the literature that rely on problem-specific trace-moment computations.

Pravesh’s notes are available at https://scribbletogether.com/whiteboard/9EF2BB4F-1701-4525-BC0B-E96984FBBBC4.