Interactive zero knowledge 3-colorability demonstration

Re:Interactive zero knowledge 3-colorability demonstration by wakamoleguy on Monday December 27, 2021 @09:04PM (#29709491)

With the second graph, Turbo mode often gets up to 60% or 70% confidence before detecting an issue. That seems odd, since I'd expect most edges in a graph to be colorable and only a few to have issues, so I'd "expect" most graphs to look fine up to that level. Is this an issue with the confidence equation and prior, or is it just expected that nobody would stop until they hit 99%+ confidence?

In other words, perhaps I'm just asking for the answer to Exercise 2!

[ Parent | on HN ]

Re:Interactive zero knowledge 3-colorability demonstration by xiphias2 on Tuesday December 28, 2021 @05:38AM (#29712322)

It's about 1-1/e (63%) as there's always 1 edge with problem, and always 1/E probability that it is revealed in on average E rounds. (1-1/E)^E -> 1/e

[ Parent | on HN ]

Re:Interactive zero knowledge 3-colorability demonstration by wakamoleguy on Monday December 27, 2021 @09:07PM (#29709504)

I suppose if you choose edges at random, then it's as likely to fail early as it is to fail late. So if you get to 70% confidence, that does seem reasonable to believe it's probably 3-colorable (but still with a big chance that it is not).

[ Parent | on HN ]