FSTTCS paper

On some Communication Complexity problems related to Threshold Functions

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.
Jaikumar Radhakrishnan
Theoretical Computer Science Group, Tata Institute of Fundamental Research, Bombay, India 400 005. jaikumar@tcs.tifr.res.in

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 a communication problem used by Karchmer and Wigderson to derive the depth version of the Khrapchenko bound. 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. Such restrictions on inputs do not have any natural formula complexity analogs; this makes the communication complexity approach more suited for our purposes.

As byproducts, we strengthen a result of Fredman and Komlás on graph covering, and obtain a Hodes-Specker like theorem for the basis {AND, OR, NOT}.