3 ms·
This is a good time to point out that the solution to GOOG rainbow color cheating isn't to reveal 4 instead of 2 and make sure only 3 colors are seen, because t
by VLM 12y ago
This is a good time to point out that the solution to GOOG rainbow color cheating isn't to reveal 4 instead of 2 and make sure only 3 colors are seen, because then GOOG wouldn't have to get paid because you'd end up with a long enough list of known pairs to not need their services, because each trial run would leak exactly one pair (assuming a trial didn't indicate GOOG cheating, obviously). This is also why GOOG has to shuffle between each and every sample.
Its interesting to think about acceptable losses in zero knowledge... If the GOOG had the computing power to solve a problem 1000x bigger than you can solve, they can leak down to only maybe 10x and it'll still economically make sense for you to play fair and pay them.
Another fun mental exercise is to analyze the info leakage rate and truth belief rate of allowing GOOG to falsify 1%, 1/3, 1/2 of all colors.
- thaumasiotes 12y agoActually, it's not necessary to build a list of known pairs that you eventually link into a solution; if a challenge reveals at least three vertices you can identify each vertex unambiguously one by one. (That's because there are only three colors, so as long as you include the same two vertices v1, v2 in every challenge, you can classify every vertex into [color of v1], [color of v2], or [color 3] as soon as you see it.) A list of pairs only becomes necessary when there are more than three colors allowed.