# Good codes decodable by linear-sized circuits?

I'm looking for error-correcting codes of the following type:

• binary codes with constant rate,

• decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of size $O(N)$, where $N$ is the encoding length.

Some background:

• This ECCC Report just came out. I haven't checked, but I expect it also gives $\Theta(N \log N)$ circuit. – Peter Shor Apr 16 '11 at 18:15
• Is $O(N)$ decoding achievable in the AWGN model or the binary model? – T.... Sep 20 '13 at 14:00
• Good binary codes which are completely linear time ($O(N)$) encodable and decodable and achieve an error rate $2^{-N}$ where $N$ is block length of the code probably requires some fundamentally new idea. The best so far is along the lines of theorem $1$ in arxiv.org/pdf/1304.4321v2.pdf. Lets see if someone improves the $2^{-N^{0.49}}$ to $2^{-N^{1-\mu}}$ in there in $N^{1+\epsilon}$ encoding and decoding time which I believe should be possible (even with $\mu=0$). However, bringing $\epsilon$ to $0$ may need more than a few tricks. – T.... Dec 4 '13 at 19:58
You should look at Tornado codes {1}, which, for any $R$ and $\epsilon>0$ and large enough $n$ can be designed to recover (with high probability) from a loss of a $(1-R)(1-\epsilon)$ fraction of bits in time proportional to $n \ln \frac{1}{\epsilon}$ (see Theorem 1 in {1}).