… The analysis of our hard instances is based on an encoding view of PPSZ. Given a formula
F on variables x1,...,xn and a satisfying assignment b, PPSZ produces an encoding of the …

… [16] have shown that there are instances on which PPSZ has exponentially small success
… has been tightened by Pudlak , Talebanfard, and myself [10]: we now know that PPSZ has …

… 8] and Schöning’s Random Walk [11] have smaller savings than PPSZ, but also of order Ω(1/k).
… We constructed close to tight hard instances for the PPSZ algorithm which uses bounded …

… PPSZ are at least Ω(1/k). Other algorithms, arguably much simpler, such as PPZ [7] and
Schöning’s Random Walk [10] have smaller savings than PPSZ… tight hard instances for the PPSZ …

… We have not found a tighter upper bound for the number of guessed variables, which can
be partly explained by the hard instance for PPSZ constructed in [SS17] with at least (1 − λ + θ)…

… Permission to make digital or hard copies of all or part of this … In Section 6, we consider cases
in which the analysis of PPSZ … which this conditional probability is much smaller than 2 3 , …

… of this conjecture: Are random instances at the threshold as hard as the worst case … k-SAT
instances behave differently from worst case k-SAT instances. On the other hand for PPSZ, the …

… that k-SAT is hard to solve for randomly chosen instances near the “critical … PPZ/PPSZ
algorithm, random k-SAT instances are provably more tractable than worst-case k-SAT instances. …

… k-SAT is hard to solve for randomly chosen instances near the “… In particular, given any
random k-SAT instance F with n … k-SAT, which might simplify the analysis as in the case of PPSZ. …

… modulo 2 that are hard for \(\mathrm {DPLL}\), \(\mathrm {PPSZ}\) … ) solvers on unsatisfiable
instances follow from lower bounds … Also, satisfiable instances are of much interest in the case …