Hacker News Reader

Comment by dataflow | Hacker News Reader

Don't you have to read all the bits first though?

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

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?

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.

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.

What if the corruption is in the last bit? Do you somehow magically know it's not in the first 3 without reading them?

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.

Yes but how would you know that without reading all 6 bits first?

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

No you don’t, you need to read at most 2 bits past corrupted one to detect it.

The question is how do you know which one is corrupted before reading all of them??

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.

Yeah and what if instead of being the 5th bit it was the 1 millionth bit that was corrupted?

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.

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??

No, it doesn't work that way.

Reply on news.ycombinator.com