A Three-Party Communication Problem

摘要

We show anΩ(log log n) lower bound on the deterministic communication complexity of the following problem. Three partiesA,B,Care given inputsx,y,z∈(Z/2)n, respectively, subject to the constraintx+y+z=1n. The function to be computed isf(x, y, z)=∨i(xi∧yi∧zi).