Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques

Let k be an even integer. We investigate the applicability of approximation techniques to the problem of deciding whether a random k-SAT formula is satisfiable. Let n be the number of propositional variables under consideration. First we show that if the number m of clauses satisfies m greater than or equal to Cn(k/2) for a certain constant C, then unsatisfiability can be certified efficiently using (known) approximation algorithms for MAX CUT or MIN BISECTION. In addition, we present an algorithm based on the Lovasz I function that within polynomial expected time decides whether the input formula is satisfiable, provided m greater than or equal to Cn(k/2). These results improve previous work by Goerdt and Krivelevich [14]. Finally, we present an algorithm that approximates random MAX 2-SAT within expected polynomial time.