Masaki Yamamoto

In [FOCS1998],

Paturi, Pudl\'ak, Saks, and Zane proposed a simple randomized algorithm

for finding a satisfying assignment of a $k$-CNF formula.

The main lemma of the paper is as follows:

Given a satisfiable $k$-CNF formula that

has a $d$-isolated satisfying assignment $z$,

the randomized algorithm finds $z$

with probability at ...
more >>>