3 ms·

This is a really interesting article for anyone interested in error correcting codes. My TL;DR is that there are some codes that are able to reconstruct data w

by foota 3y ago

This is a really interesting article for anyone interested in error correcting codes. My TL;DR is that there are some codes that are able to reconstruct data with a fixed number of queries (i.e., limiting the fan out of reads for reconstruction). There are two types of these, locally correctable and locally decodable codes. Locally decodable codes allow reconstructing any part of the original message with a fixed number of reads, while locally correctable codes allow reconstructing parts of the code words in the same way. In particular, the article discusses two query and three queries. The best known algorithms in the past for both of these (two and three queries) for either locally correctable codes or locally decodable codes was the Reed-Muller code, however these codes are exponential in length wrt the length of the original message. In 2003 it was found that it's not possible to do better for two queries than Reed-Muller codes, but in ~2009, Yekhanin and Efremenko independently discovered algorithms that allow for locally decodable three query codes shorter than this (though not linear in length, I think). Now, it's been shown that there are no locally correctable three query codes that are better than Reed-Muller in length, using a technique based on satisfiability.

orlp 3y ago
Now I think the interesting barriers are those with log n queries or sqrt n queries.
- foota 3y ago
  I think there's a few areas of improvement. One is for yet better three query locally decodable codes (like I said, I think it's still not (sub)linear in space, which is likely a blocker for real use), another is for larger constants, and then as you note, for non-constant queries. My impression though is that the more interesting question is for larger constants (e.g., four query, etc.,). edit: interestingly, it looks like an earlier paper from overlapping authors proves a lower bound of k^3 (where k is the original message's length) for 3 query locally decodable codes: https://arxiv.org/abs/2308.15403 https://arxiv.org/abs/2308.15403 (ah, this was actually linked in the article but I missed it).

by foota 3y ago

orlp 3y ago

Now I think the interesting barriers are those with log n queries or sqrt n queries.

foota 3y ago
I think there's a few areas of improvement. One is for yet better three query locally decodable codes (like I said, I think it's still not (sub)linear in space, which is likely a blocker for real use), another is for larger constants, and then as you note, for non-constant queries. My impression though is that the more interesting question is for larger constants (e.g., four query, etc.,). edit: interestingly, it looks like an earlier paper from overlapping authors proves a lower bound of k^3 (where k is the original message's length) for 3 query locally decodable codes: https://arxiv.org/abs/2308.15403 https://arxiv.org/abs/2308.15403 (ah, this was actually linked in the article but I missed it).