Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits

摘要

A sampling procedure for a distribution P over {0,1}' is a function C : {0, 1}~n → {0,1}~t such that the distribution C(U_n) (obtained by applying C on the uniform distribution U~n) is the "desired distribution" P. Let n > r ≥ t = n~(Ω(1)). An ∈-nb-PRG (denned by Dubrov and Ishai [2006]) is a function G : {0, 1}~r→ {0,1}~n such that for every C : {0,1}~n → {0, 1}~t in some class of "interesting sampling procedures," C'(U_r) = C(GiU_r)) is ∈-close to C(U~n) in statistical distance. We construct poly-time computable nb-PRGs with r = O(t) for poly-size circuits relying on the assumption that there exists β > 0 and a problem L in E = DTIME(2~(O(n))) such that for every large enough n, nonde-terministic circuits of size 2~(βn) that have NP-gates cannot solve L on inputs of length n. This assumption is a scaled nonuniform analog of (the widely believed) EXP ≠ Σ(~p_2), and similar assumptions appear in various contexts in derandomization. Previous nb-PRGs of Dubrov and Ishai have r = Ω(t~2) and are based on very strong cryptographic assumptions or, alternatively, on nonstandard assumptions regarding incompressibility of functions on random inputs. When restricting to poly-size circuits C : [0, 1]~n → {0, 1}~t with Shannon entropy H(C(U_n)) ≤k,for t.>k = n~(Ω(1)), our nb-PRGs have r = O(k). The nb-PRGs of Dubrov and Ishai use seed length r = Q(k~2) and require that the probability distribution of C(U_n) is efficiently computable. Our nb-PRGs follow from a notion of "conditional PRGs," which may be of independent interest. These are PRGs where G(U_r) remains pseudorandom even when conditioned on a "large" event {A(G(U_r)) = 1), for an arbitrary poly-size circuit A A related notion was considered by Shaltiel and Umans [2005] in a different setting, and our proofs use ideas from that paper, as well as ideas of Dubrov and Ishai. We also give an unconditional construction of poly-time computable nb-PRGs for poly(n)-size, depth d circuits C : {0,1}~n → {0,1}~t with r = O(l log~(d+O(1) n). This improves upon the previous work of Dubrov and Ishai that has r ≥ t~2. This result follows by adapting a recent PRG construction of Trevisan and Xue [2013] to the case of nb-PRGs. We also show that this PRG can be implemented by a uniform family of constant-depth circuits with slightly increased seed length.