ISSN:
1432-0622
Keywords:
Communication complexity
;
Sum-type functions
;
Exponential rank quasi direct sum
;
Quasi outer product
;
Missing dimension
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract For two matrix operations, calledquasi-direct sum andquasi-outer product, we determine their deviations from multiplicative behaviour of the rank. The second operation arises in the determination of the function table for so-called sum-type functions such as the Hamming distance. A consequence of the corresponding rank formula is, that the frequently used log rank can be a very poor bound for two-way communication complexity. Instead, as was shown in [9], a certainexponential rank gives often excellent or even optimal bounds.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01200149
Permalink