"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
Abstract:
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 http://eccc.hpi-web.de/report/2016/037/