All reports by Author Evgeny Dantsin:

__
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

__
TR01-012
| 4th January 2001
__

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov#### Algorithms for SAT and Upper Bounds on Their Complexity

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 >>>

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

We survey recent algorithms for the propositional

satisfiability problem, in particular algorithms

that have the best current worst-case upper bounds

on their complexity. We also discuss some related

issues: the derandomization of the algorithm of

Paturi, Pudlak, Saks and Zane, the Valiant-Vazirani

Lemma, and random walk ...
more >>>