Finding a satisfying assignment for planted NAE-E3-SAT using a voting style algorithm

A random planted formula is constructed by fixing a certain planted assignment to the variables, and then adding only clauses that are satisfied by the planted assignment. The purpose of such approach is to generate a random-like formula that is guaranteed to have a satisfying assignment. The random planted 3-SAT has received significant attention. In particular, it has been shown that when containing sufficiently many clauses, it is solvable with high probability in polynomial time. In this work we obtain a similar result for the random planted Not-All-Equal-SAT problem, which is defined in the same way except that the clauses added are the Not-All-Equal clauses. We follow one of the aforementioned approaches by Krivelevich and Vilenchik. In the case of NAE-SAT the first step, voting, makes no sense. We show that the same result can be achieved by solving the MAX-CUT problem in the co-occurrence graph of the formula.