Ronen Shaltiel

Seedless extractors for samplable distributions were first constructed under a very strong complexity-theoretic hardness assumption: that E=DTIME(2^O(n)) is hard for exponential-size circuits with oracle access to a fixed level of the polynomial hierarchy. That construction applies to sources with min-entropy k=(1−γ)n for an arbitrarily small constant γ>0. Subsequent works weakened the hardness assumption and improved the min-entropy threshold to k=n^1−γ and then to k=n^Ω(1), though these improvements again relied on hardness against circuits with oracle access to the polynomial hierarchy. We introduce a new approach to constructing extractors for samplable distributions, inspired by constructions of two-source extractors. Our approach relies on a new, incomparable hardness assumption involving only deterministic circuits, and reduces the task of constructing extractors for samplable distributions to that of constructing explicit non-malleable extractors with short seed length. The new assumption has the same flavor as the classic assumption that E is hard for exponential-size circuits. Specifically, we assume that there exists a constant 0<α0, there exists a constant c′ and an explicit extractor Ext:{0,1}ⁿ→{0,1} with error ε for distributions of min-entropy at least c′logn that are samplable by circuits of size n^c. The key observation underlying our construction is that for a samplable source, the set of bad seeds for a non-malleable extractor is efficiently recognizable. We use this observation to show that, in the relevant two-source extractor constructions, the second source can be replaced by the truth table of a sufficiently hard function. This yields an unexpected connection between two-source extractors and extractors for samplable distributions, paralleling the classical connection between extractors and pseudorandom generators in the opposite direction.

Codes for poly-size circuits: Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a p-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon’s binary symmetric channel (BSC), but weaker than Hamming’s channels which are computationally unbounded. The goal of this direction is to construct explicit codes (namely, codes with poly-time encoding and decoding algorithms) with rate R(p)=1−H(p) (matching the capacity of the BSC, and beating the capacity of codes for Hamming’s channels). This goal implies circuit lower bounds, and specifically that E=DTIME(2^O(n)) does not have poly-size circuits (and therefore explicit constructions need to be based on hardness assumptions). We give the first explicit construction of such codes for poly-size channels. Specifically, for every 0 ≤ p < 1/4, there are explicit codes with rate R(p)=1−H(p), assuming E does not have size 2^Ω(n) nondeterministic circuits. This hardness assumption was introduced in the context of hardness vs. randomness tradeoffs, and is by now standard in complexity theory. Our result builds on, and improves the previous work of Guruswami and Smith, and Shaltiel and Silbak (FOCS 2022). (These works gave a randomized Monte-Carlo construction, rather than explicit codes). Functions that are hard to sample on low entropy distributions: A key component in our codes (that may be of independent interest) is a new complexity theoretic notion of hard to sample functions (HTS): We say that a function f on n bits is an HTS for circuits of size n^c, if there exists a constant c′>c, such that for every randomized circuit A of size n^c that samples a distribution (X,Y) with (X) ≥ c′ · logn, it holds that Pr[Y=f(X)] ≤ 1/n^c. This is inspired by works by Viola on the complexity of distributions (SICOMP 2012, 2020), in which X is the uniform distribution. Here, we allow A to choose any distribution X (except for distributions X with very low min-entropy) and note that a circuit A of size n^c, may be hardwired with ≈ n^c outputs of f, and therefore, can easily produce pairs (X,f(X)) for a distribution X, with (X) ≈ c logn. Building on classical works on “hardness amplification” (and using many additional tools and ideas from pseudorandomness) we show that if E does not have size 2^Ω(n) nondeterministic circuits, then for every constant c, there is an HTS that is computable in time (n^c). Our codes are obtained by using our HTS (as well as additional tools and ideas) to achieve explicit constructions (under the hardness assumption) of several components in the code of Shaltiel and Silbak, replacing previously obtained randomized Monte-Carlo constructions of these components. We then need to revisit the codes of Shaltiel and Silbak, and significantly modify the construction and analysis, so that they work with the weaker components that we are able to explicitly construct.