I am looking for tools to lower bound the deterministic, blackboard, number-in-hand communication complexity of a certain function which is roughly speaking $f : \{0,1\}^k \times \ldots \times \{0,1\}^k \to \{0,1\}$, where $f$ has $k$ arguments each known by one player in the protocol. I have proven that both the nondeterministic and co-nondeterministic communication complexity of $f$ in the number-in-hand model is small, $\widetilde O(k)$. But, I conjecture that the deterministic complexity should be as high as possible, $\Omega(k^2)$.

Initially, I had hoped that one could resolve the conjecture by embedding a hard two-player communication problem in this model. But, while I haven't finished the proof, I think now it may be the case that for any partition of the $k$ inputs of $f$ between Alice and Bob, the two-player communication complexity is $\widetilde O(k)$ (this was recently shown true for some similar functions).

So, my question is: are there any simple, natural functions $g : \{0,1\}^k \times \ldots \times \{0,1\}^k \to \{0,1\}$ for which these types of complexity results hold? Namely, any two-player version of the problem is easy (i.e., $O(k)$ complexity), but the $k$-player number-in-hand version is known to be hard (i.e., $\Omega(k^2)$ complexity)?

(One popular number-in-hand problem is Set-Disjointness, but this does not seem suitable because strong lower bounds require each player to hold many more bits of input, and because the co-nondeterministic complexity of Set-Disjointness is too easy for the problem to embed in the $f$ I'm interested in. Earlier, my interest in this same $f$ spurred this question, which I would also still appreciate answers to, since the functions brought up in that thread are still somewhat unwieldy. However, if my current suspicion about the two-player protocols for $f$ is correct, then the thing that my prior question asks for will be too strong to possibly work: I'd still need something only hard specifically for $k$-player number-in-hand where each player holds $k$ bits.)



Your Answer

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

Browse other questions tagged or ask your own question.