Improved Explicit Near-Optimal Codes in the High-Noise Regimes

We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from 1-ε 2 fraction of errors and list decodable from 1 -ε fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding algorithms. Our contributions are as follows.