RANK FORMULAS FOR CERTAIN PRODUCTS OF MATRICES

被引：0

作者：

AHLSWEDE, R ^{[1
]}

CAI, N ^{[1
]}

机构：

[1] UNIV BIELEFELD,FAK MATH,W-4800 BIELEFELD 1,GERMANY

来源：

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING | 1993年 / 4卷 / 04期

关键词：

COMMUNICATION COMPLEXITY; SUM-TYPE FUNCTIONS; EXPONENTIAL RANK QUASI DIRECT SUM; QUASI OUTER PRODUCT; MISSING DIMENSION;

D O I：

10.1007/BF01200149

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

For two matrix operations, called quasi-direct sum and quasi-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 certain exponential rank gives often excellent or even optimal bounds.

引用

页码：253 / 261

页数：9