Laboratory of Mathematical Logic at PDMI

Cреда, 28 июня, 203. Начало в 12:00.

Докладчик: Navid Talebanfard (Saarland University and the Cluster of Excellence, MMCI).

Тема: Tighter Hard Instances for PPSZ.

Abstract

We construct uniquely satisfiable k-CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most (2+ϵ)/k; the saving of an algorithm on an input formula with n variables is the largest γ such that the algorithm succeeds (i.e. finds a satisfying assignment) with probability at least 2−(1−γ)n. Since PPSZ (both weak and strong) is known to have savings of at least π2+o(1)6k, this is optimal up to the constant factor. In particular, for k=3, our upper bound is 20.333…n, which is fairly close to the lower bound 20.386…n of Hertli [SIAM J. Comput.'14]. We also construct instances based on linear systems over F2 for which strong PPSZ has savings of at most O(log(k)k). This is only a log(k) factor away from the optimal bound. Our constructions improve previous savings upper bound of O(log2(k)k) due to Chen et al. [SODA'13].

https://arxiv.org/abs/1611.01291