Tight Bounds for Conservative Pointer JumpingResearch Paper
In the number-on-the-forehead (NOF) model of communication of Chandra, Furst and Lipton (CFL83), an input is split into parts and each of players sees every part except the one on its own forehead. Lower bounds in this model are hard to prove because the players' views overlap so much, and they would be valuable: by Yao (Yao90), Håstad and Goldmann (HG91…