1
$\begingroup$

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)?$

Improve this question
$\endgroup$
1
  • 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$
    – mathworker21
    Jun 30, 2022 at 15:42

0

Reset to default

Your Answer

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