On some communication complexity problems related to threshold functions

Halldórsson, Magnús M. ; Radhakrishnan, Jaikumar ; Subrahmanyam, K. V. (1993) On some communication complexity problems related to threshold functions Lecture Notes in Computer Science, 761 . pp. 248-259. ISSN 0302-9743

Full text not available from this repository.

Official URL: http://www.springerlink.com/index/7416788g8n463375...

Related URL: http://dx.doi.org/10.1007/3-540-57529-4_58

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.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:89531
Deposited On:27 Apr 2012 14:16
Last Modified:27 Apr 2012 14:16

Repository Staff Only: item control page