Loading jsMath...
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: 3645
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