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 \emph{beating the capacity of codes for Hamming's channels}). This goal implies circuit lower bounds, and specifically that $\text{E}=\text{DTIME}(2^{O(n)}$) does not have poly-size circuits.

We give the first explicit construction of such codes for poly-size channels. Specifically, for every $0 c$, such that for every randomized circuit $A$ of size $n^c$ that samples a distribution $(X,Y)$ with $H_{\infty}(X) >= c' \cdot \log n$, it holds that $\Pr[Y=f(X)] \le \frac{1}{n^c}$.

This is inspired by a related notion introduced by Viola (SICOMP 2012), 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 $\approx n^c$ outputs of $f$, and therefore, can easily produce pairs $(X,f(X))$ for a distribution $X$, with $H_{\infty}(X) \approx c \log n$.

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^{\Omega(n)}$ nondeterministic circuits, then for every constant $c$, there is an HTS that is computable in time $\poly(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 works with the weaker components that we are able to explicitly construct.

Corrected Typo in the statement of Thm 2.25, and some minor edits.

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 \emph{beating the capacity of codes for Hamming's channels}). This goal implies circuit lower bounds, and specifically that $\text{E}=\text{DTIME}(2^{O(n)}$) does not have poly-size circuits.

We give the first explicit construction of such codes for poly-size channels. Specifically, for every $0 c$, such that for every randomized circuit $A$ of size $n^c$ that samples a distribution $(X,Y)$ with $H_{\infty}(X) >= c' \cdot \log n$, it holds that $\Pr[Y=f(X)] \le \frac{1}{n^c}$.

This is inspired by a related notion introduced by Viola (SICOMP 2012), 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 $\approx n^c$ outputs of $f$, and therefore, can easily produce pairs $(X,f(X))$ for a distribution $X$, with $H_{\infty}(X) \approx c \log n$.

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^{\Omega(n)}$ nondeterministic circuits, then for every constant $c$, there is an HTS that is computable in time $\poly(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 works with the weaker components that we are able to explicitly construct.

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 \emph{beating the capacity of codes for Hamming's channels}). This goal implies circuit lower bounds, and specifically that $\text{E}=\text{DTIME}(2^{O(n)}$) does not have poly-size circuits.

We give the first explicit construction of such codes for poly-size channels. Specifically, for every $0 c$, such that for every randomized circuit $A$ of size $n^c$ that samples a distribution $(X,Y)$ with $H_{\infty}(X) >= c' \cdot \log n$, it holds that $\Pr[Y=f(X)] \le \frac{1}{n^c}$.

This is inspired by a related notion introduced by Viola (SICOMP 2012), 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 $\approx n^c$ outputs of $f$, and therefore, can easily produce pairs $(X,f(X))$ for a distribution $X$, with $H_{\infty}(X) \approx c \log n$.

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^{\Omega(n)}$ nondeterministic circuits, then for every constant $c$, there is an HTS that is computable in time $\poly(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 works with the weaker components that we are able to explicitly construct.

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 \emph{beating the capacity of codes for Hamming's channels}). This goal implies circuit lower bounds, and specifically that $\text{E}=\text{DTIME}(2^{O(n)}$) does not have poly-size circuits.

We give the first explicit construction of such codes for poly-size channels. Specifically, for every $0 c$, such that for every randomized circuit $A$ of size $n^c$ that samples a distribution $(X,Y)$ with $H_{\infty}(X) >= c' \cdot \log n$, it holds that $\Pr[Y=f(X)] \le \frac{1}{n^c}$.

This is inspired by a related notion introduced by Viola (SICOMP 2012), 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 $\approx n^c$ outputs of $f$, and therefore, can easily produce pairs $(X,f(X))$ for a distribution $X$, with $H_{\infty}(X) \approx c \log n$.

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^{\Omega(n)}$ nondeterministic circuits, then for every constant $c$, there is an HTS that is computable in time $\poly(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 works with the weaker components that we are able to explicitly construct.