Assume that Alice and Bob have sets $A,B\subseteq[n]$ of size $|A|=|B|=k$.

In the simultaneous protocol, they both send a message to Carol (that doesn't observe $A$ and $B$) which needs to determine whether $A\cap B$. Let us denote the required (to succeed with probability $3/4$) number of bits from the messages by $S(DIST_k^n)$.

In this paper, Hastad and Wigderson proved that $S(DIST_k^n)=O(4^k)$, which gives a non trivial bound if $k=o(\log n)$.

I'm interested in a case where $k=\sqrt n$ and am wondering if it is possible to get a $o(n)$ bit bound.

Is $S(DIST_{\sqrt n}^n)=o(n)?$

  • 6
    $\begingroup$ Can't both Alice and Bob literally just send Carol exactly what their subset is with only $\sqrt{n}\log n$ bits? $\endgroup$ Jun 30, 2022 at 15:42


Your Answer

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