Re:Researchers Defeat Randomness to Create Ideal Code
by dataflow on Friday November 26, 2021 @04:41PM
(#29354437)
Don't you have to read all the bits first though?
[ Parent
| on HN ]
Re:Researchers Defeat Randomness to Create Ideal Code
by tromp on Friday November 26, 2021 @05:14PM
(#29354755)
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."
Re:Researchers Defeat Randomness to Create Ideal Code
by dataflow on Friday November 26, 2021 @05:21PM
(#29354813)
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?
Re:Researchers Defeat Randomness to Create Ideal Code
by dmurray on Friday November 26, 2021 @04:49PM
(#29354514)
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.
Re:Researchers Defeat Randomness to Create Ideal Code
by ajb on Friday November 26, 2021 @07:29PM
(#29355847)
You 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.
Re:Researchers Defeat Randomness to Create Ideal Code
by dataflow on Friday November 26, 2021 @04:52PM
(#29354543)
What if the corruption is in the last bit? Do you somehow magically know it's not in the first 3 without reading them?
Re:Researchers Defeat Randomness to Create Ideal Code
by cdtwigg on Friday November 26, 2021 @05:19PM
(#29354802)
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.
Re:Researchers Defeat Randomness to Create Ideal Code
by dataflow on Friday November 26, 2021 @05:28PM
(#29354888)
Yes but how would you know that without reading all 6 bits first?
Re:Researchers Defeat Randomness to Create Ideal Code
by netizen-936824 on Friday November 26, 2021 @06:46PM
(#29355522)
You wouldn't, as long as the bits are received sequentially. I think the idea is that, depending on where the corruption is, you only need to read up to two bits past the corrupted one
Re:Researchers Defeat Randomness to Create Ideal Code
by mirekrusin on Saturday November 27, 2021 @02:33AM
(#29358335)
No you don’t, you need to read at most 2 bits past corrupted one to detect it.
Re:Researchers Defeat Randomness to Create Ideal Code
by dataflow on Saturday November 27, 2021 @02:35AM
(#29358343)
The question is how do you know which one is corrupted before reading all of them??
Re:Researchers Defeat Randomness to Create Ideal Code
by mirekrusin on Saturday November 27, 2021 @03:28AM
(#29358579)
You don't need to read 1 million bits to detect 5th being corrupted one, you will know it after reading 3 * 5 = 15 bits.
Re:Researchers Defeat Randomness to Create Ideal Code
by dataflow on Saturday November 27, 2021 @03:31AM
(#29358601)
Yeah and what if instead of being the 5th bit it was the 1 millionth bit that was corrupted?
Re:Researchers Defeat Randomness to Create Ideal Code
by mirekrusin on Saturday November 27, 2021 @05:45AM
(#29359172)
For 1 million bits message where millionth bit is corrupted last bit doesn't have to be read, in general in 3 replica coding, reading first 2 is enough if they are the same - reading last one will have no effect.
Re:Researchers Defeat Randomness to Create Ideal Code
by dataflow on Saturday November 27, 2021 @05:48AM
(#29359189)
For heaven's sake... how in the world would you know it's the millionth bit that's corrupted without scanning all 999,999 other bits at least once?!?!
Do you data streams always come magically tagged with sentences like "Hey, watch out for bits 999,998-1,000,000, but all my other bits are intact so you can skip them!" or something??! You somehow "know" the error is in the final 3 bits and not in the earlier 999,997 bits because... magic??
Re:Researchers Defeat Randomness to Create Ideal Code
by mirekrusin on Saturday November 27, 2021 @12:24PM
(#29361740)
No, it doesn't work that way.