On some communication complexity problems related to threshold functions

Abstract

We study the computation of threshold functions using formulas over the basis {AND, OR, NOT}, with the aim of unifying the lower bounds of Hansel, Krichevskii, and Khrapchenko. For this we consider communication complexity problems related to threshold function computation. -We obtain an upper bound for the communication complexity problem used by Karchmer and Wigderson to derive the depth version of the lower bound of Khrapchenko. This shows that their method, as it is, cannot give better lower bounds. - We show how better lower bounds can be obtained if the referee (who was ignored in the Karchmer-Wigderson method) is involved in the argument. - We show that the difficulty of the communication task persists even if the parties are required to operate correctly only for certain special inputs. We also consider the one-sided communication complexity of these problems and obtain tight lower bounds.