Results on communication complexity classes (Q1190990)

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.