A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

New answers tagged


During the first phase of the algorithm, the players zoom in on a high-entropy coordinate. They exchange $O(1)$ bits, and stop at each step with probability $\Omega(\epsilon^2/\log^2(1/\epsilon))$ (here we use independence). Hence this phase uses up at most $O(\log^2(1/\epsilon)/\epsilon^2)$ bits in expectation. The second phase uses $O(n\epsilon)$ bits. In ...

Top 50 recent answers are included