🧩 📊 Answers and discussion for this week's #WeaklyQuiz on Alice, Bob, and their attempt to avoid jail by using communication complexity!
So, what's the answer?
As 21% of you answered at the time I write this, by communicating only 1 bit 👋 Alice and Bob can succeed with probability at least 50%
1/
So, what's the answer?
As 21% of you answered at the time I write this, by communicating only 1 bit 👋 Alice and Bob can succeed with probability at least 50%
1/
Comments
But the guarantee here is a "one-sided error": if a=b then A and B succeed with proba ONE. If a,b differ, then proba 1/2.
https://bsky.app/profile/ccanonne.bsky.social/post/3lis4cjtm722j
Thanks to the lava lamp, that is...
All what's coming below (and more):
📝 https://github.com/ccanonne/weeklyquiz/blob/main/2025-01-equality.md
2/
- without 🎲 at all, if Alice and Bob want to decide if their 2 lists are equal? With o(n) communication, they're screwed.
- with 🎲 (but not shared one!)? With o(log n) communication, they're screwed.
- with 🎲 (shared one!)? With O(1) communication, they're good!
3/
Alice and Bob use a "good" error-correcting code to map their inputs a, b to codewords C(a), C(b), so that if a≠b then C(a),C(b) are far.
Then they use shared 🎲 to look at the same (random) coordinate of their codeword
4/
📝 https://github.com/ccanonne/weeklyquiz/blob/main/2025-01-equality.md
And, of course, communication complexity is fascinating! There are *many* great resources, among which a recent book by Rao and Yehudaoff: https://www.cambridge.org/core/books/communication-complexity/5F44993E3B2597174B71D3F21E748443
(free draft: https://yehudayoff.net.technion.ac.il/files/2016/03/book.pdf)
5/end
If a≠ b, then they say they're the same with probability ≤ 1/2
(It will allow them to be absolutely sure they're different with probability 1/2; never absolutely sure they're the same)