Sum-of-Squares Refutation Threshold for Regular SORT_4 instances
For a random regular instance of the Constraint Satisfaction Problem (CSP) based on the SORT_4 predicate, we give an explicit value d such that
if the degree of the CSP is less than d, then the degree-2 Sum-of-Squares relaxation fails to refute the CSP with high probability. Assuming
a conjectured generalization of Bordenave's theorem for random lifts, we also give a refutation algorithm for when the degree of the CSP is
greater than d, thus showing that this d is a "sharp threshold".