Randomized algorithm for 2kCNF satisfiability problem

Question

The problem: Let a formula in $\varphi\in 2kCNF$ where there's an assignment $\alpha$ such that for every clause, $l$ in $\varphi$, $\alpha$ satisfies at least $k$ literals of $l$. Suggest a randomized algorithm for finding a satisfying assignment for such $\varphi$.

So basically I've read about the $WALKSAT$ algoritm which starts with some random assignment, $\alpha_1$ and for every iteration chooses randomly an unsatisfied clause, $l$ of $\varphi(\alpha)$ and a literal of $l$. Then, it flips this literal in $\alpha_1$, getting a new assignment, $\alpha_2$.

We repeat this process within a time bound $t$ or until a satisfying assignment has been found.

I've understood that this algorithm could be suitable here. I need to show that there's a probability of $\frac{1}{2}$ finding a satisfying assignment (probably after amplification)

I think we should look at the hamming distance of $\alpha, \alpha^t$ where $\alpha$ is the assignment as described in the question and $\alpha^t$ is unsatisfying assignment after $t$ iterations.

I'd be glad if you could guide from this point.

Thanks!

Answer 1

The analysis of Schöning's algorithm (see for example these CMU lecture notes) relies on the fact that if $\alpha$ is a satisfying assignment, $\beta$ is any assignment, and $C$ is an unsatisfied $k$-clause, then flipping a random variable decreases the distance between $\beta$ and $\alpha$ with probability at least $1/k$. In your case, you can get a better guarantee since $\alpha$ satisfies half the literals in every clause.