# Valentin Kabanets (Theory Seminar)

"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)