期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2020
卷号：2020
页码：1-15
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：Set disjointness (Disj) is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including – most famously – interactive randomised communication with bounded error (R), the problem requires much communication. In this work we were looking for a variation of Disj, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its R-complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection (II). The following list of its properties seem to let II resist the old lower bound techniques: • the domain of II is A×B, the product of the players’ individual input spaces; • A×B only contains intersecting pairs of subsets; • the input comes from the uniform distribution over A×B;• A×B is chosen in a randomised fashion, both A and B being uniformly-random
subsets of 2
[n] of size 2
n
Θ(1)
.
In particular, complexity analysis of II cannot be based on the hardness of Disj (as
no pair in A×B is disjoint); moreover, it cannot be based on any argument based on
discrepancy (including corruption, smooth discrepancy and the like), as the problem
allows for a cover of A×B by n perfectly-monochromatic rectangles.
We are using an ad hoc technique to show that II is ultimately hard: it requires
Ω(log|A|) bits of interactive randomised communication. Besides its ability – apparently unique – to capture the complexity of the inevitable intersection, the new
technique can also be applied to other “search-like” problems (including Disj), thus
providing new insight into their communicational hardness.
