^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Tsinghua University^{3} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

In 1998, Paturi, Pudl´ak, Saks, and Zane presented PPSZ, an elegant randomized algorithm for k-SAT. Fourteen years on, this algorithm is still the fastest known worst-case algorithm. They proved that its expected running time on k-CNF formulas with n variables is at most 2(1−k)n, where k 2 (1/k). So far, no exponential lower bounds at all have been known. In this paper, we construct hard instances for PPSZ. That is, we construct satisfiable k-CNF formulas over n variables on which the expected running time is at least 2(1−k)n, for k 2 O(log2 k/k).

ISBN:

9781611972511

Type:

Conference paper

Language:

English

Published in:

Proceedings of the Annual Acm-siam Symposium on Discrete Algorithms, 2013, p. 1253-1263

Main Research Area:

Science/technology

Publication Status:

Published

Series:

Annual a C M - S I a M Symposium on Discrete Algorithms. Proceedings

Review type:

Peer Review

Conference:

ACM-SIAM symposium on Disrete AlgorithmsSymposium on Discrete Algorithms, 2013