Results on communication complexity classes
type: Item
instance of: scholarly article
title: Results on communication complexity classes
zbMATH Open document ID: 0762.68023
DOI: 10.1016/0022-0000(92)90025-E
author: Walter L. Ruzzo
author: Tak-Wah Lam
published in: Journal of Computer and System Sciences
publication date: 1992-09-27T00:00:00Z
review text: Communication complexity classes corresponding to fixed and optimal partitions of the input are considered. The first result is a simple technique allowing translation of most known separation and containment results for the fixed partition model to the more difficult optimal partition model. It is proved that given any ``paddable'' language \(L\), one can construct a ``shifted'' language \(L_{sf}\) so that (up to a multiplicative factor) \(CC_{fixed}(L)\) coincides with \(CC_{opt}(L_{sf})\). Here \(L\) is paddable if a length \(n\) string of \(L\) can be embedded into any \(n\) bit positions of a longer string, with the remaining bit positions filled (``padded'') with some easy determined sequence of values (most of languages that have been used to separate fixed partition classes are paddable). The shifted version \(L_{sf}\) of a language \(L\subseteq\{0,1\}:2*\) consists of all triples \((x,y,z)\) where \(z=2[\log n]\) and \((SHIFT(x,z)y)\in L\); here \(SHIFT(x,z)\) is the right cyclic shift of \(x\) by \(z\) positions. The second result concerns the alternating communication complexity of the block - equality function. This function, given two \(n\times n\) matrices \(X\) and \(Y\), computes \(1\) iff for some \(i\), the \(i\)-th rows of X and Y coincide. The function has an obvious \(\exists\forall\)-protocol with poly-log movies: guess the index \(i\) and check the equality of rows. Applying the hashing functions it is proved that (surprisingly) this function has also an \(\forall\exists\)-protocol with poly-log movies.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 58812
zbMATH Keywords: separation results
zbMATH Keywords: optimal partition model
zbMATH Keywords: hierarchies
zbMATH Keywords: alternating communication complexity hierarchies
zbMATH Keywords: Communication complexity
Wikidata QID: Q58063096
reviewed by: Stasys Jukna
MaRDI profile type: Publication
cites work: Information Transfer under Different Sets of Protocols
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Optimal edge ranking of trees in linear time
cites work: Communication complexity
cites work: Probabilistic communication complexity
cites work: The polynomial-time hierarchy
cites work: Complete sets and the polynomial-time hierarchy
full work available at URL: 0022-0000(92)90025-e
OpenAlex ID: W2174130830
description: scientific article; zbMATH DE number 58812