Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity

Simon Mackenzie, Abdallah Saffidine

In communication complexity the input of a function $f:X\times Y\to Z$ is distributed between two players Alice and Bob. If Alice knows only $x\in X$ and Bob only $y\in Y$,…