Correction of samplable additive errors
Kenji Yasunaga · 2014
We study the correctability of efficiently samplable errors. Specifically, we consider samplable additive-error channels, where unbounded-weight errors are sampled by a polynomial-time algorithm, and added to the channel input in an oblivious way. Assuming the existence of one-way functions, there are samplable distributions Z over {0, 1}nwith entropy nεfor 01-(m+log(1-ε))/n. Finally, we observe that small-biased distributions are not correctable by high-rate codes, and hence there is a small-biased Z with entropy m that is not correctable for rate R > 1-m/n+(2 log n+O(1))/n. To derive these results, we use relations between error-correcting codes and other notions such as data compression and randomness condensers.