[HN Gopher] Researchers Defeat Randomness to Create Ideal Code
___________________________________________________________________
Researchers Defeat Randomness to Create Ideal Code
Author : digital55
Score : 35 points
Date : 2021-11-26 01:46 UTC (21 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| [deleted]
| [deleted]
| pizza wrote:
| Somehow 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?
| unbanned wrote:
| Dupe of 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 wrote:
| flag the other one
| (https://news.ycombinator.com/item?id=29350983)
| ajb wrote:
| Hmm I think Leonid Levin did something similar:
| 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
| dataflow wrote:
| I 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 wrote:
| Good 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 wrote:
| Don't you have to read all the bits first though?
| tromp wrote:
| From https://en.wikipedia.org/wiki/Locally_testable_code :
|
| "Clearly, any valid codeword should be accepted as a
| codeword, but strings that are not codewords could be only
| one bit off, which would require many (certainly more than
| a constant number) probes. To account for this, testing
| failure is only defined if the string is off by at least a
| set fraction of its bits. This implies words of the code
| must be longer than the input strings by adding some
| redundancy."
| dataflow wrote:
| I'm not sure I'm really following how that answers my
| question unfortunately. Are they assuming O(n)
| corruptions? Distributed randomly in the string?
| dmurray wrote:
| No, 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.
| dataflow wrote:
| What if the corruption is in the last bit? Do you somehow
| magically know it's not in the first 3 without reading
| them?
| cdtwigg wrote:
| In this formulation I believe the last bit would also be
| repeated 3 times, and you'd have to read those three bits
| to detect corruption.
| dataflow wrote:
| Yes but how would you know that without reading all 6
| bits first?
___________________________________________________________________
(page generated 2021-11-26 23:01 UTC)