The threshold for SDP-refutation of random regular NAE-3SAT.

Yash Deshpande Andrea Montanari Ryan O'Donnell Tselil Schramm Subhabrata Sen

Published in: CoRR (2018)

Keyphrases

satisfiability problem
semidefinite programming
theorem proving
search algorithm
sat solvers
evolutionary algorithm
linear programming
randomly generated
stochastic local search
threshold selection
search strategies
phase transition
propositional satisfiability