Recent work in error correcting codes
Nov. 28th, 2021 02:15 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
joshuazelinskyThere's been some really neat recent work on error correcting codes. There's a Quanta article going around but it doesn't do a great job explaining some of the background ideas.
Since Shannon and Hamming's work about 60 years ago, there's been a lot of interest in error correcting codes. These are ways of embedding data which allows one to detect or correct errors in transmission. Natural languages do this mostly automatically. For example, if I inclde a typo in this sentence, you can probably notice it and figure out what I wanted. But they aren't perfect at this. If I write "I have a pet bat" it might mean "I have a pet cat" with a typo, but you can't be certain. Error correcting codes let you handle at least some number of errors of a certain type.
But how do you do this? We'll one naive thing is to just repeat each bit in your message a whole bunch of times. Let's say we repeat everything three times. So if you get "III hhhaaavvvee aaa pppeeettt ccbaaattt" you can be pretty sure that I meant was "cat" not "bat". To do this in a mathematically precise fashion, we generally talk about this in terms of strings of 0s and 1s, rather than letters, but the same idea applies.
Notice that in order for this code to work we had to send things which are three times as long as our original message, and we can correct any single typo. That's not great. We can do a bit better. For example, Hamming codes only increase the message size a teeny bit and still allow us to do a good job correcting a single error like this.
There's some technical subtlety here between "detecting" and "correcting" an error. For example, if you get the sentence "I have a pet dat" you can tell there's a least one error, but correcting it is tough. Should that have read "dog" (two errors), "cat" (one error) or "bat" (one error)- all you can tell is that "dat" is not a type of animal so something has gone wrong here. You can guess what is most likely, but you can't be certain.
One issue is that we have an existence proof of some very good codes. These codes are good in the sense that they don't require messages to be much longer than the message you intend to send, and also they let you detect even large numbers of errors. The argument essentially works by roughly speaking picking an assignment rule at random, and showing that with non-zero probability the code will do a good job. But actually constructing such codes is tough. This work roughly speaking manages to create one of those close to ideal sets of codes that we knew had to exist but had trouble constructing. They did so by using some ideas from graph theory that had previously been used to construct codes but had not succeeded at making really good codes. But these are very good, due to some new insights and careful constructions. (There are some details here I'm skipping; the above statement isn't strictly speaking completely accurate since it turns out these codes are a bit long.) One really nice thing about the codes they constructed is that errors can be seen by only checking a small part of the message.
It is worth noting that the work here is using a variant of "expander graphs" and one of the authors of this is Irit Dinur. She previously used expander graphs to prove a version of the PCP theorem which essentially says that you can turn any mathematical proof into a proof which can be verified with a high probability by only checking a small section of the proof chosen at random. So there's some definite commonality of theme here. Expander graphs roughly speaking are graphs where if you walk randomly on them, you can end up very far away with a high chance, even though any given node in the graph has only a few edges. They've been involved in a lot of neat stuff the last few years including some somewhat connected randomness amplification work.
Since Shannon and Hamming's work about 60 years ago, there's been a lot of interest in error correcting codes. These are ways of embedding data which allows one to detect or correct errors in transmission. Natural languages do this mostly automatically. For example, if I inclde a typo in this sentence, you can probably notice it and figure out what I wanted. But they aren't perfect at this. If I write "I have a pet bat" it might mean "I have a pet cat" with a typo, but you can't be certain. Error correcting codes let you handle at least some number of errors of a certain type.
But how do you do this? We'll one naive thing is to just repeat each bit in your message a whole bunch of times. Let's say we repeat everything three times. So if you get "III hhhaaavvvee aaa pppeeettt ccbaaattt" you can be pretty sure that I meant was "cat" not "bat". To do this in a mathematically precise fashion, we generally talk about this in terms of strings of 0s and 1s, rather than letters, but the same idea applies.
Notice that in order for this code to work we had to send things which are three times as long as our original message, and we can correct any single typo. That's not great. We can do a bit better. For example, Hamming codes only increase the message size a teeny bit and still allow us to do a good job correcting a single error like this.
There's some technical subtlety here between "detecting" and "correcting" an error. For example, if you get the sentence "I have a pet dat" you can tell there's a least one error, but correcting it is tough. Should that have read "dog" (two errors), "cat" (one error) or "bat" (one error)- all you can tell is that "dat" is not a type of animal so something has gone wrong here. You can guess what is most likely, but you can't be certain.
One issue is that we have an existence proof of some very good codes. These codes are good in the sense that they don't require messages to be much longer than the message you intend to send, and also they let you detect even large numbers of errors. The argument essentially works by roughly speaking picking an assignment rule at random, and showing that with non-zero probability the code will do a good job. But actually constructing such codes is tough. This work roughly speaking manages to create one of those close to ideal sets of codes that we knew had to exist but had trouble constructing. They did so by using some ideas from graph theory that had previously been used to construct codes but had not succeeded at making really good codes. But these are very good, due to some new insights and careful constructions. (There are some details here I'm skipping; the above statement isn't strictly speaking completely accurate since it turns out these codes are a bit long.) One really nice thing about the codes they constructed is that errors can be seen by only checking a small part of the message.
It is worth noting that the work here is using a variant of "expander graphs" and one of the authors of this is Irit Dinur. She previously used expander graphs to prove a version of the PCP theorem which essentially says that you can turn any mathematical proof into a proof which can be verified with a high probability by only checking a small section of the proof chosen at random. So there's some definite commonality of theme here. Expander graphs roughly speaking are graphs where if you walk randomly on them, you can end up very far away with a high chance, even though any given node in the graph has only a few edges. They've been involved in a lot of neat stuff the last few years including some somewhat connected randomness amplification work.
