Search Results

Impagliazzo and Wigderson (STOC 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 (STOC 2010) observed that many such algorithms are obtained from randomized time T algorithms, for T < 2^o(n), with large one-sided error 1-epsilon, for epsilon=2^(-alpha*n), that are repeated 1/epsilon times to yield a constant-error 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 epsilon-HSG (Hitting-Set Generator) H:{0,1}^(O(log(n)) + log(1/epsilon) -> {0,1}^n, implying that time T randomized algorithms with one-sided error 1-epsilon can be simulated in deterministic time poly(T)/epsilon. In particular, under this hardness assumption, the fastest known constant-error randomized algorithm for k-SAT (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 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. Applebaum et al. (CCC 2015) showed that "black-box techniques" cannot achieve poly(n)-time computable epsilon-PRGs (Pseudo-Random 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)-re-PRG for a circuit C if (1-epsilon)*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)-re-PRGs with arbitrary polynomial stretch, epsilon=n^-O(1) and delta=2^(-n^Omega(1)). We also construct PRGs with relative error that fool non-boolean 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).

A circuit C compresses a function f:{0,1}^n -> {0,1}^m if given an input x in {0,1}^n the circuit C can shrink x to a shorter l-bit string x' such that later, a computationally-unbounded solver D will be able to compute f(x) based on x'. In this paper we study the existence of functions which are incompressible by circuits of some fixed polynomial size s=n^c. Motivated by cryptographic applications, we focus on average-case (l,epsilon) incompressibility, which guarantees that on a random input x in {0,1}^n, for every size s circuit C:{0,1}^n -> {0,1}^l and any unbounded solver D, the success probability Pr_x[D(C(x))=f(x)] is upper-bounded by 2^(-m)+epsilon. While this notion of incompressibility appeared in several works (e.g., Dubrov and Ishai, STOC 06), so far no explicit constructions of efficiently computable incompressible functions were known. In this work we present the following results: 1. Assuming that E is hard for exponential size nondeterministic circuits, we construct a polynomial time computable boolean function f:{0,1}^n -> {0,1} which is incompressible by size n^c circuits with communication l=(1-o(1)) * n and error epsilon=n^(-c). Our technique generalizes to the case of PRGs against nonboolean circuits, improving and simplifying the previous construction of Shaltiel and Artemenko (STOC 14). 2. We show that it is possible to achieve negligible error parameter epsilon=n^(-omega(1)) for nonboolean functions. Specifically, assuming that E is hard for exponential size Sigma_3-circuits, we construct a nonboolean function f:{0,1}^n -> {0,1}^m which is incompressible by size n^c circuits with l=Omega(n) and extremely small epsilon=n^(-c) * 2^(-m). Our construction combines the techniques of Trevisan and Vadhan (FOCS 00) with a new notion of relative error deterministic extractor which may be of independent interest. 3. We show that the task of constructing an incompressible boolean function f:{0,1}^n -> {0,1} with negligible error parameter epsilon cannot be achieved by "existing proof techniques". Namely, nondeterministic reductions (or even Sigma_i reductions) cannot get epsilon=n^(-omega(1)) for boolean incompressible functions. Our results also apply to constructions of standard Nisan-Wigderson type PRGs and (standard) boolean functions that are hard on average, explaining, in retrospective, the limitations of existing constructions. Our impossibility result builds on an approach of Shaltiel and Viola (SIAM J. Comp., 2010).