ON THE DISTRIBUTIONAL COMPLEXITY OF DISJOINTNESS

被引：267

作者：

RAZBOROV, AA

机构：

[1] Steklov Mathematical Institute, Vavilova, 42, GSP-1, 117966, Moscow

来源：

THEORETICAL COMPUTER SCIENCE | 1992年 / 106卷 / 02期

关键词：

D O I：

10.1016/0304-3975(92)90260-M

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that the distributional communication complexity of the predicate "disjointness" with respect to a very simple measure on inputs is OMEGA(n).

引用

页码：385 / 390

页数：6