Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions

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(2O(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 nc, if there exists a constant c′>c, such that for every randomized circuit A of size nc that samples a distribution (X,Y) with (X) ≥ c′ · logn, it holds that Pr[Y=f(X)] ≤ 1/nc. 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 nc, may be hardwired with ≈ nc 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 (nc). 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.