Edward Hirsch

Recently there was a significant progress in

proving (exponential-time) worst-case upper bounds for the

propositional satisfiability problem (SAT).

MAX-SAT is an important generalization of SAT.

Several upper bounds were obtained for MAX-SAT and

its NP-complete subproblems.

In particular, Niedermeier and Rossmanith recently

...
more >>>

Edward Hirsch

During the past three years there was an explosion of algorithms

solving MAX-SAT and MAX-2-SAT in worst-case time of the order

c^K, where c<2 is a constant, and K is the number of clauses

in the input formula. Such bounds w.r.t. the number of variables

instead of the number of ...
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 >>>