  Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the
property that spectral/SDP algorithms can efficiently refute random instances
when the constraint density is a large constant (with high probability). But do
these methods work immediately above the "satisfiability threshold", or is
there still a range of constraint densities for which random NAE-3SAT instances
are unsatisfiable but hard to refute?
  We show that the latter situation prevails, at least in the context of random
regular instances and SDP-based refutation. More precisely, whereas a random
$d$-regular instance of NAE-3SAT is easily shown to be unsatisfiable (whp) once
$d \geq 8$, we establish the following sharp threshold result regarding
efficient refutation: If $d < 13.5$ then the basic SDP, even augmented with
triangle inequalities, fails to refute satisfiability (whp), if $d > 13.5$ then
even the most basic spectral algorithm refutes satisfiability~(whp).
