Improved efficiency for covering codes matching the sphere-covering bound
Aditya Potukuchi, Yihan Zhang · 2020
A covering code is a subset C ⊆ {0, 1}nwith the property that any z E {0, 1}nis close to some c E C in Hamming distance. For every c, δ > 0, we show a construction of a family of codes with relative covering radius δ+ε and rate 1-H(δ) with block length at most exp(O((1/c) log(1/c))) for every c> 0. This improves upon a folklore construction which only guaranteed codes of block length exp(1/ε2). The main idea behind this proof is to find a distribution on codes with relatively small support such that most of these codes have good covering properties.