I'm trying to lower bound the worst-case deterministic communication complexity of some special class of functions on $n$ variables, and I've shown that for every function $f$ in the class: $N^1(f) = O(\sqrt{n})$ and $N^0(f)=O(\sqrt{n})$, where $N^1$ and $N^0$ are the nondeterministic and co-nondeterministic communication complexity of $f$, respectively. I conjecture that the worst-case deterministic complexity $D(f) = \Omega(n)$, which (from the general fact that $D(g) \le N^0(g)\cdot N^1(g)$) is as high as possible given what I know so far.

My question is this: what are some natural functions $g$ such that $N^0(g) = O(\sqrt{n})$, $N^1(g)=O(\sqrt{n})$, and $D(g) = \Omega(n)$? I am trying to reduce my problem to some such function $g$, and if my conjecture is true, such a $g$ must have this value of $N^0$ and $N^1$.

Kushilevitz and Nisan give one such example (4.13), which can be phrase like this: Alice and Bob both have $\sqrt{n}\times\sqrt{n}$ matrices, and $g$ outputs $1$ if and only if some row of both matrices are equal. This $g$ might suffice, but I haven't gotten the reduction right yet, and I'm having trouble finding any different examples to try. This property seems fairly natural, as it sort of "splits the hardness" perfectly evenly between verifying $0$ and verifying $1$, so I'm wondering if any other natural example exist.


1 Answer 1


A natural problem where $D\approx N^0N^1$ was proved only recently is the clique vs independent set problem: Given an $n$-vertex graph, Alice gets a clique, while Bob gets an independent set, and their goal is to decide whether their sets are disjoint or intersect in a single vertex.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.