Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-027 | 19th February 2005 00:00

Derandomization of PPSZ for Unique-$k$-SAT

RSS-Feed




TR05-027
Authors: Daniel Rolf
Publication: 3rd March 2005 17:43
Downloads: 3440
Keywords: 


Abstract:

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)$ deterministic running time at most.



ISSN 1433-8092 | Imprint