Hacker News Reader

Comment by dataflow | Hacker News Reader

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?

View on HN

Imagine taking a book off a shelf, flipping to a random page, then pointing at a random word on that page. Without any knowledge of the rest of the page or book you can tell whether that word is spelled correctly and exists in the dictionary. That is local testability.

With code words you need to be able to distinguish where the code word starts and stops and how long it is. For more complex code words not all bit combinations are valid just like not all combinations of letters are valid words.

The example given at the beginning of the article doesn't really go far enough. Yes if you repeat a bit 3 times, you can tell its corrupted if any of the three don't match (ignore the correction part of it because that is not part of local testability).

What the article doesn't cover in its example is that if you have a message that is a full gigabyte. You can skip to any part of that message (as long as you know the index you're at), find the beginning of the code word (it will have index % 3 == 0) and the next three bits and verify whether those have been corrupted or not as well.

It's the original you care about, not the encoding. Suppose you have a code such that at least 50% of the encoded bits must be corrupted to prevent a good decoding of the source. If the encoding is that corrupted, if you choose 20 bits at random to examine, there's less than 1/1000000 chance that you chose one of the corrupted ones. So this code might be one in which for any 20 bits, you can tell if they form part of a valid codeword.

> If the encoding is that corrupted, if you choose 20 bits at random to examine, there's less than 1/1000000 chance that you chose one of the corrupted ones.

Is there a typo somewhere here? I'm confused what you're saying. So if my message is 40 bits long and you randomly pick 20 bits to examine, there's a less than one-in-a-million chance that you choose a corrupted bit?

Why? Wouldn't that be an almost 100% chance (= 1 - (20/40 * 19/39 * 18/38 * ...))? Or in terms of whether you recovered the correct value, wouldn't that be a 50% chance (20/40)? Sorry this probably sounds really dumb but I feel like I'm not understanding what you intended to write.

Yes, if the message is only 40 bits long there is a 100% chance. But the point is that you still only need 20 bits even if the message is 100000 bits long

Because if 50% of bits are corrupted, each bit has a >50% chance of being corrupted, so With 20 bits you have only a 1 in 2^20 chance of missing all the corrupted bits.

The 20 bits don't allow you do correct anything, BTW. To do that you need a locally decodable code. What we are talking about here is the ability to detect corruption of the original data.

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

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