[Computational Complexity] Can we make this problem FUN?
- Consider the following cute problem:
Alice, Bob, and Carol each have a number between 0 and 1,000,000,000,000 on their forehead. Everyone can see the numbers that are NOT on their own forehead. Call the three numbers x,y,z. They wish to determine if x+y+z is divisible by 1,000,000,000,000. There is an easy solution: Alice can just say Bob, your number is .... This would take 13 digits of communication. Can they do better?Chandra, Furst, and Lipton showed that if instead of 1,000,000,000,000 was replaced by n, and if n is large, then do this in roughly \sqrt n bits. They were more interested in the k-party lower bound of &omega(1) since this leads to lower bounds on branching programs. (NOTE: They studied a variant of the the problem above, but everything they did applies hear also.) See their paper or my writeup for JUST the upper bound or my writeup of the upper and lower boundand its application to branching programs for more information.
The problem stated above with people having numbers on their foreheads sounds like it could be a fun problem for the layperson. BUT: The problem with this problem for the layperson is two fold: (1) The original problem involves 3-free sets. While our community might say Wow, an application of stuff coming out of van der Waerden's theorem (or at least I would say that), the layperson would not think of it or care. (2) Frankly, I don't know if 13 digits numbers are big enough for the asymptotics to kick in and give a better answer than 13.
SO- here is my challenge: Is there a solution to this problem (or perhaps one with larger numbers) where the solution is non-trivial--- that is, you do not communicate all of the numbers, but is also FUN! FUN means you can tell it to your non-mathematical-nephew, or perhaps your 10-years-old-great-niece-who-likes-math. Quite okay if its far worse than \sqrt(n).
Posted By GASARCH to Computational Complexity at 6/10/2009 12:19:00 PM