Strong refutation of semi-random Boolean CSPs

For a fixed integer k > 1, the Boolean k-XOR problem consists of a system of linear equations mod 2 with each equation involving exactly k variables. We give an algorithm to strongly refute *semi-random* instances of the Boolean k-XOR problem on n variables that have n^{k/2} poly(log n) equations. (In a semi-random k-XOR instance, the equations can be arbitrary and only the right-hand sides are random.) Via known reductions, this yields an efficient strong refutation algorithm for 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.

When k is even, refutation of k-XOR follows via a natural flattening to a 2-XOR instance on n^{k/2} variables. Such a straightforward approach is, however, not available for odd k. The fully random case of k-XOR for odd k was refuted in prior work via spectral methods employing intricate trace-moment computations. We first give a simpler proof for the purely random case relying only on an off-the-shelf matrix Bernstein inequality. Springboarding off the random case, we identify a combinatorial property of random k-XOR instances that makes spectral refutation work, and solve the semi-random case by reduction to a collection of 2-XOR instances and employing spectral upper bounds that utilize the Booleanity of the assignment.

Joint work with Jackson Abascal and Pravesh Kothari.