All reports by Author Alexander Wolpert:

__
TR05-102
| 13th September 2005
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

__
TR05-030
| 12th February 2005
__

Evgeny Dantsin, Alexander Wolpert#### An Improved Upper Bound for SAT

__
TR04-017
| 22nd February 2004
__

Evgeny Dantsin, Alexander Wolpert#### Derandomization of Schuler's Algorithm for SAT

__
TR03-072
| 15th September 2003
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Algorithms for SAT based on search in Hamming balls

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>

Evgeny Dantsin, Alexander Wolpert

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

Evgeny Dantsin, Alexander Wolpert

Recently Schuler \cite{Sch03} presented a randomized algorithm that

solves SAT in expected time at most $2^{n(1-1/\log_2(2m))}$ up to a

polynomial factor, where $n$ and $m$ are, respectively, the number of

variables and the number of clauses in the input formula. This bound

is the best known ...
more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We present a simple randomized algorithm for SAT and prove an upper

bound on its running time. Given a Boolean formula F in conjunctive

normal form, the algorithm finds a satisfying assignment for F

(if any) by repeating the following: Choose an assignment A at

random and ...
more >>>