All reports by Author Daniel Rolf:

__
TR05-159
| 14th November 2005
__

Daniel Rolf#### Improved Bound for the PPSZ/SchÃ¶ning-Algorithm for $3$-SAT

__
TR05-027
| 19th February 2005
__

Daniel Rolf#### Derandomization of PPSZ for Unique-$k$-SAT

__
TR03-054
| 2nd July 2003
__

Daniel Rolf#### 3-SAT in RTIME(O(1.32793^n)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses

Daniel Rolf

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, SchÃ¶ning proved ... more >>>

Daniel Rolf

The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formulas can be found in expected running time at most $\Oc(1.3071^n).$ Using the technique of limited independence, we can derandomize this algorithm yielding $\Oc(1.3071^n)$ ... more >>>

Daniel Rolf

This paper establishes a randomized algorithm that finds a satisfying assignment for a satisfiable formula $F$ in 3-CNF in $O(1.32793^n)$ expected running time. The algorithms is based on the analysis of so-called strings, which are sequences of 3-clauses where non-succeeding clauses do not share a variable and succeeding clauses share ... more >>>