Lower bounds on the randomized communication complexity of read-once functions
type: Item
instance of: scholarly article
title: Lower bounds on the randomized communication complexity of read-once functions
zbMATH Open document ID: 1229.68042
author: Nikos Leonardos
author: Michael Saks
published in: Computational Complexity
publication date: 2011-02-18T00:00:00Z
review text: A read-once formula is a Boolean formula using the logical connectives AND and OR with the property that every variable appears exactly once. A read-once threshold formula is more general in that it can also use threshold gates. The paper establishes lower bounds for the two-party communication complexity of functions computed by read-once formulae and by read-once threshold formulae. The lower bounds are of the form \(n/c^d\), where \(n\) is the number of variables, \(d\) is the depth of the formula, and \(c\) is a constant. The proofs use information-theoretical methods.
reviewed by: Marius Zimand
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94A15
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 5853287
zbMATH Keywords: and/or trees
zbMATH Keywords: communication complexity
zbMATH Keywords: information theory
zbMATH Keywords: read-once formulae
MaRDI profile type: Publication
full work available at URL: s00037-010-0292-2
OpenAlex ID: W2097234068
DOI: 10.1007/S00037-010-0292-2
description: scientific article; zbMATH DE number 5853287