Dominik Scheder: Exponential Lower Bounds for the PPSZ k-SAT Algorithm

Lunch is served at 12:00 noon (register at doodle.com/29v43i4yy38rpi52 by Thursday Feb 14 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for roughly one more hour of a possibly slightly more technical presentation.

Abstract

In 1998, Paturi, Pudlak, 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 - epsilon_k)n), where epsilon_k = Omega(1/k). So far, no exponential lower bounds at all have been known.

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 - epsilon_k)n), for epsilon_k in O(log^2 (k) / k).

This is joint work with Shiteng Chen, Navid Talebanfard, and Bangsheng Tang.