Lower bounds on the randomized communication complexity of read-once functions

Nikos Leonardos, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We prove lower bounds on the randomized two-party communication complexity of functions that arise from readonce Boolean formulae. A read-once Boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. in the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. in this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/c d(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant c in the denominator.

Original languageEnglish (US)
Title of host publicationProceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Pages341-350
Number of pages10
DOIs
StatePublished - 2009
Event2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 - Paris, France
Duration: Jul 15 2009Jul 18 2009

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Country/TerritoryFrance
CityParis
Period7/15/097/18/09

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Lower bounds on the randomized communication complexity of read-once functions'. Together they form a unique fingerprint.

Cite this