Communication complexity of some number theoretic functions Original Research Article

We show that the communication complexity of the parity of the sum of binary digits of x+yx+y is at least 0.085667…n+O(1)0.085667…n+O(1) where xx and yy are nn-bit integers. We also obtain a nontrivial (but weaker) lower bound on the parity of the total number of prime divisors of x+yx+y counted with multiplicity.