Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-149 | 13th November 2023 16:35

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

RSS-Feed




Revision #1
Authors: Ronen Shaltiel, Jad Silbak
Accepted on: 13th November 2023 16:35
Downloads: 107
Keywords: 


Abstract:

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.


Paper:

TR23-149 | 5th October 2023 18:14

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





TR23-149
Authors: Ronen Shaltiel, Jad Silbak
Publication: 5th October 2023 18:14
Downloads: 210
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint