Valentin Kabanets (Theory Seminar)

kabanets.jpg"Pseudorandomness when the odds are against you: Derandomizing the PPSZ algorithm for k-SAT"
Valentin Kabanets
(Simon Fraser University)
Monday, April 24th, 2016, 2:00 pm
EBU3B, Room 4258
Impagliazzo and Wigderson (1997) showed that if E=DTIME(2^{O(n)) requires size 2^{\Omega(n)} circuits, then every time T constant-error randomized algorithm can be simulated deterministically in time poly(T). However, such polynomial slowdown is a deal breaker when T=2^{\alpha n}, for a constant alpha>0, as is the case for some randomized algorithms for NP-complete problems. Paturi and Pudlak (2010) observed that many such algorithms are obtained from randomized time T algorithms, for T< 2^{o(n)}, with large one-sided error 1-eps, for eps=2^{- alpha  n}, that are repeated  1/eps times to yield a constant-error randomized algorithm running in time T/eps=2^{alpha+o(1))  n}.

Our main result is that if E requires size 2^{Omega(n)} nondeterministic circuits, then there is a poly(n)-time eps-HSG (Hitting-Set Generator) H: {0,1}^{O(log n) + log(1/\eps)} \to {0,1}^n, implying that time T randomized algorithms with one-sided error  1-eps  can be simulated in deterministic time poly(T)/eps. In particular, under this hardness assumption, the fastest known constant-error randomized algorithm for k-SAT (for k> 3) by Paturi, Pudlak, Saks, and Zane (2005) can be made deterministic with essentially the same time bound. This is the first hardness versus randomness trade-off for algorithms for NP-complete problems. We address the necessity of our assumption by showing that HSGs with very low error imply hardness for nondeterministic circuits with ``few'' nondeterministic bits.

Joint work with Sergei Artemenko, Ronen Shaltiel (Haifa), and Russell Impagliazzo (UCSD)

Paper Link