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. 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}.