3 ms·

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