Re:'Magical' Error Correction Scheme Proved Inherently Ineff...
by orlp on Wednesday January 10, 2024 @05:57AM
(#38938861)
Now I think the interesting barriers are those with log n queries or sqrt n queries.
Re:'Magical' Error Correction Scheme Proved Inherently Ineff...
by foota on Wednesday January 10, 2024 @03:21PM
(#38942587)
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 (ah, this was actually linked in the article but I missed it).
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.