6 ms·
Researchers Defeat Randomness to Create Ideal Code
- unbanned 5y agoDupe of https://news.ycombinator.com/item?id=29350983 https://news.ycombinator.com/item?id=29350983 – this current submission has a lower ID and was submitted earlier. Neither have comments so far but both are on the front page. @dang if you read this, can this one be marked as as a dupe?
- tlarkworthy 5y agoflag the other one (https://news.ycombinator.com/item?id=29350983 https://news.ycombinator.com/item?id=29350983)
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- pizza 5y agoSomehow this reminds me of Polar codes (used in the 5G control protocol), the first code to provably approach the Shannon limit (iiuc). It works by turning a physical channel into N virtual channels, and it uses the polar coding algorithm to increase the noisiness of some virtual channels, while decreasing the noisiness of others. So you need to pick which virtual channels to listen to, depending on the noisiness characteristics of the environment. And it kind of uses a simple recursive strategy to generate these codes as a simple mixture of inputs. If I understand correctly, this approach is kind of using a recursive checksum-like system to use local bits to verify the integrity of the code globally?
- deleted 5y ago[deleted]
- dataflow 5y agoI don't understand the definition of local testability. Could someone explain? Like say I send you 1 million bits of information, and the 5th one is corrupted. The proposition is you can somehow figure this out by examining only a small number of bits? How in the world is that possible? You have no idea which bit might be corrupted a priori, so wouldn't you have to at least read all of them once?
- mirekrusin 5y agoGood naive example is provided at the beginning - you repeat each bit 3 times – you'll be protected against single bit flip by taking majority vote (value of other 2 bits).
- dataflow 5y agoDon't you have to read all the bits first though?
- dmurray 5y agoNo, you just have to read the first 3 bits, if the corruption is in those. But yeah, you can't detect a single-bit corruption if you haven't actually read that bit.
- ajb 5y agoYou can't detect single bit corruption of the encoding without reading that bit. But what you care about is whether the encoding is sufficiently corrupted that you can't decode the original.
- dataflow 5y agoWhat if the corruption is in the last bit? Do you somehow magically know it's not in the first 3 without reading them?
- cdtwigg 5y ago
- ajb 5y agoHmm I think Leonid Levin did something similar: https://www.cs.bu.edu/fac/lnd/expo/holo.htm https://www.cs.bu.edu/fac/lnd/expo/holo.htm Not sure yet what this one is doing that that one doesn't. (Edited to add) Having read further, it seems that this code is close to optimal in rate and distance too. The link above is actually for probabilistically checkable proofs, which are similar, and the article thinks this is likely to lead to advances there too
- floatingatoll 5y agoSee also: Locally Testable Codes with constant rate, distance, and locality https://arxiv.org/abs/2111.04808 https://arxiv.org/abs/2111.04808 For example, from heading “High Dimensional Expansion”: > The current paper is mainly elementary and almost self-contained (with the exception of Section 6 which uses the existence of some Ramanujan Cayley graphs with specific properties and can be taken as a black box). But it came up as a result of a much longer and intensive journey. Some interesting open problems were left aside along the way. It is, therefore, worthwhile to give the story here.
- vcdimension 5y agoHere is one application that this research could be applied to: https://github.com/Parchive/par2cmdline https://github.com/Parchive/par2cmdline https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive