# 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:

• Andy, coincidentally, I also came across this issue about a year ago and after a brief amount of searching, concluded that the question was open. So, I'm also curious if an answer's known. Apr 12 '11 at 23:45
• This ECCC Report just came out. I haven't checked, but I expect it also gives $\Theta(N \log N)$ circuit. Apr 16 '11 at 18:15
• Is $O(N)$ decoding achievable in the AWGN model or the binary model?
– Mr.
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.
– Mr.
Dec 4 '13 at 19:58
• Have a look at Expander codes. These codes achieve linear time coding and decoding. The linearity is w.r.t to the size of the codeword. But I am not sure if they can be decoded using linear circuits. Apr 28 '14 at 11:28

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}).