The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known
algorithm for the k-SAT problem, for every k> 3. For 3-SAT, a tiny improvement over PPSZ …

PPSZ, for long time the fastest known algorithm for 𝑘-SAT, works by going through the
variables of the input formula in random order; each variable is then set randomly to 0 or 1 …

Multiple known algorithmic paradigms (backtracking, local search and the polynomial
method) only yield a 2 n (1-1/O (k)) time algorithm for k-SAT in the worst case. For this …

Fine-grained complexity studies problems that are" hard" in the following sense. Consider a
computational problem for which existing techniques easily give an algorithm running in a …

We construct k-CNFs with m variables on which the strong version of PPSZ k-SAT algorithm,
which uses resolution of width bounded by O (√{log log m}), has success probability at most …

We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input
formula is chosen randomly. We build upon the algorithms of Sch {\"{o}} ning 1999 and …

Itsykson and Sokolov in 2014 introduced the class of DPLL (⊕) algorithms that solve
Boolean satisfiability problem using the splitting by linear combinations of variables modulo …

In this thesis we study satisfiability algorithms and connections between algorithms and
circuit lower bounds. We give new results in the following three areas: Oracles and …

All known SAT-solving paradigms (backtracking, local search, and the polynomial method)
only yield a 2 n (1− 1/O (k)) time algorithm for solving k-SAT in the worst case, where the big …

It has been hypothesized that $ k $-SAT is hard to solve for randomly chosen instances near
the" critical threshold", where the clause-to-variable ratio is $2^ k\ln 2-\theta (1) $. Feige's …