Сложность декодирования низкоплотностных кодов при передаче по каналу со стираниями

Доказывается, что существуют низкоплотностные коды длины $n$ с декодированием, исправляющим все стирания до кратности $\alpha n$ при сложности порядка $n\ln n$. Показано, что отношение $\alpha n$ к кодовому расстоянию, соответствующему границе Варшамова–Гилберта, может быть оценено снизу величиной, изменяющейся от 0,33 до 0,66 при росте скорости передачи от 0 до 1.