On the Power of Multiplexing in Number-on-the-Forehead Protocols

Eldar Aharoni, Eyal Kushilevitz

We study the direct-sum problem for $k$-party ``Number On the Forehead'' (NOF) deterministic communication complexity. We prove several positive results, showing that the complexit…