Research

From danielrolf.com

Jump to: navigation, search
Home

Index

During my computer-science studies, I focused on the well-known k-SAT problem. As far as I know (Mar-2007), I am (still) record holder for the best upper bound for 3-SAT with respect to the number of variables, and I am record holder for the best deterministic upper bound for Unique-k-SAT as well. If that is not true anymore, please inform me as I am constantly getting out of touch with k-SAT since I finished my PhD-thesis.

Contents

[edit] PhD-Thesis

[edit] Algorithms for the Satisfiability Problem

May 2006: We discuss serveral algorithms for k-SAT. This work includes all the papers you find here under the 'Papers' section.

Download PDF

[edit] Diploma-Thesis

[edit] 3-SAT in RTIME(1.32971^n): Improving Initial Assignments for Randomized Local Search for 3-SAT Using Joint Clause Pairs

January 2003: This paper has been my first result on 3-SAT.

Download PDF

[edit] Student Research Project

[edit] Randomisierte Algorithmen

November 2002: German -- Existenz von Graphen mit hoher Taillenweite und hohem Durchschnittsgrad, Existenz von Graphen mit hoher Taillenweite und hoher chromatischer Zahl, String Verifikation, Randomisiertes Paging

Download PDF

[edit] Papers

[edit] 3-SAT in RTIME(1.32793^n): Improving Randomized Local Search by Initializing Strings of 3-Clauses

July 2003: 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.

Download PDF

[edit] Derandomization of PPSZ for Unique-k-SAT

February 2005: This paper establishes a deterministic algorithm that finds a satisfying assignment for a uniquely satisfiable formula F in 3-CNF in O(1.3071^n) running time.

Download PDF

[edit] Improved Bound for the PPSZ/Schöning-Algorithm for 3-SAT

November 2005: This paper establishes a bound that a satisfying assignment for a satisfiable formula F in 3-CNF can be found in O(1.32216^n) running time.

Download PDF



<= Work | Goodies =>