Error Correcting Codes that Achieve BSC Capacity Against Channels that are 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. Guruswami and Smith gave an explicit Monte-Carlo construction of codes with optimal rate of R(p) = 1-H(p) that achieve list-decoding in this scenario. Here, "explicit Monte-Carlo" means that both encoding and decoding algorithms run in polynomial time. However, the encoding and decoding algorithms also receive a uniformly chosen string of polynomial length (which is chosen and published, once and for all, in a pre-processing stage) and their correctness is guaranteed w.h.p. over this random choice. Guruswami and Smith asked whether it is possible to obtain uniquely decodable codes for poly-size channels with rate that beats the Gilbert-Varshamov bound R GV (p) = 1 -H(2p). We give an affirmative answer, Specifically:

• For every 0 ≤ p < 1 4 , we give an explicit Monte-Carlo construction of uniquely-decodable codes with optimal rate R(p) = 1 -H(p). This matches the rate achieved by Guruswami and Smith for the easier task of list-decoding, and also matches the capacity of binary symmetric channels. Moreover, this rate is strictly larger than that of codes for the standard coding scenario (namely, uniquely-decodable codes for Hamming channels).

• Even ignoring explicitness, our result implies a characterization of the capacity of poly-size channels, which was not previously understood.

Our technique builds on the earlier list-decodable codes of Guruswami and Smith, achieving uniquedecoding by extending and modifying the construction so that we can identify the correct message in the list. For this purpose we use ideas from coding theory and pseudorandomness, specifically:

• We construct codes for binary symmetric channels that beat the Gilbert-Varshamov bound, and are "evasive" in the sense that a poly-size circuit that receives a random (or actually pseudorandom) string, cannot find a codeword within relative distance 2p. This notion of evasiveness is inspired by the recent work of Shaltiel and Silbak (STOC 2021) on codes for space bounded channels.

• We develop a methodology (that is inspired by proofs of t-wise independent tail inequalities, and may be of independent interest) to analyze random codes, in scenarios where the success of the channel is measured in an additional random experiment (as in the evasiveness experiment above).

• We introduce a new notion of "small-set non-malleable codes" that is tailored for our application, and may be of independent interest.