Abstract
Impagliazzo and Wigderson (STOC 1997) showed that if E=DTIME(2^O(n)) requires size 2^Omega(n) circuits, then every time T constanterror 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 NPcomplete problems. Paturi and Pudlak (STOC 2010) observed that many such algorithms are obtained from randomized time T algorithms, for T < 2^o(n), with large onesided error 1epsilon, for epsilon=2^(alpha*n), that are repeated 1/epsilon times to yield a constanterror randomized algorithm running in time T/epsilon=2^((alpha+o(1))*n).
We show that if E requires size 2^Omega(n) nondeterministic circuits, then there is a poly(n)time epsilonHSG (HittingSet Generator) H:{0,1}^(O(log(n)) + log(1/epsilon) > {0,1}^n, implying that time T randomized algorithms with onesided error 1epsilon can be simulated in deterministic time poly(T)/epsilon. In particular, under this hardness assumption, the fastest known constanterror randomized algorithm for kSAT (for k > 3) by Paturi et al. (J. ACM 2005) can be made deterministic with essentially the same time bound. This is the first hardness versus randomness tradeoff for algorithms for NPcomplete 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.
Applebaum et al. (CCC 2015) showed that "blackbox techniques" cannot achieve poly(n)time computable epsilonPRGs (PseudoRandom Generators) for epsilon=n^omega(1), even if we assume hardness against circuits with oracle access to an arbitrary language in the polynomial time hierarchy. We introduce weaker variants of PRGs with relative error, that do follow under the latter hardness assumption. Specifically, we say that a function G:{0,1}^r > {0,1}^n is an (epsilon,delta)rePRG for a circuit C if (1epsilon)*Pr[C(U_n)=1]  delta < Pr[C(G(U_r)=1] < (1+epsilon)*Pr[C(U_n)=1] + delta. We construct poly(n)time computable (epsilon,delta)rePRGs with arbitrary polynomial stretch, epsilon=n^O(1) and delta=2^(n^Omega(1)). We also construct PRGs with relative error that fool nonboolean distinguishers (in the sense introduced by Dubrov and Ishai (STOC 2006)).
Our techniques use ideas from Paturi and Pudlak (STOC 2010), Trevisan and Vadhan (FOCS 2000), Applebaum et al. (CCC 2015). Common themes in our proofs are "composing" a PRG/HSG with a combinatorial object such as dispersers and extractors, and the use of nondeterministic reductions in the spirit of Feige and Lund (Comp. Complexity 1997).
BibTeX  Entry
@InProceedings{artemenko_et_al:LIPIcs:2016:5837,
author = {Sergei Artemenko and Russell Impagliazzo and Valentine Kabanets and Ronen Shaltiel},
title = {{Pseudorandomness When the Odds are Against You}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {9:19:35},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5837},
URN = {urn:nbn:de:0030drops58375},
doi = {10.4230/LIPIcs.CCC.2016.9},
annote = {Keywords: Derandomization, pseudorandom generator, hittingset generator, relative error}
}
Keywords: 

Derandomization, pseudorandom generator, hittingset generator, relative error 
Collection: 

31st Conference on Computational Complexity (CCC 2016) 
Issue Date: 

2016 
Date of publication: 

19.05.2016 