Set-disjointness is one of the most fundamental and widely studied problems in the area of communication complexity. In this problem, each party $i$ receives a set $S_i\subseteq [N]$. The goal is to determine whether $\bigcap S_i$ is empty via communication between players. The decision version simply asks if the common intersection is empty or not, while the search version asks players to find an element $a\in \bigcap S_i$ if it exists. Both versions give wide applications in diverse areas.
In this paper, we focus on the communication complexity of the search version under product distributions in the number-in-hand (NIH) model. For the decision version, Babai, Frankl, and Simon (FOCS 86) proposed an $\Omega(\sqrt{N})$ lower bound under product distributions for the two-party setting, and was extended to $k$-party setting $\Omega(N^{1-1/k}/k^2)$ by Dershowitz, Oshman, and Roth (STOC 21).
For the search version, though it is well-motivated by several applications, lower bounds were less known due to some technical obstacles. In this paper, we study the following natural problem, which was further motivated by Bauer, Farshim, and Mazaheri (CRYPTO 18) from cryptography motivations: there are $k$ players, and each of them receives a (random) set of size $\approx N^{1-\alpha_{i}}$; the goal is to find a common element. We prove that:
if each party holds a random set of size $\approx N^{1-\alpha_i}$, the communication complexity lower bound is $\Omega(N^{\sum_i\alpha_i - \mathop{\max}_i\{\alpha_i\}}/k)$.
Furthermore, we show that our lower bounds are indeed almost tight, up to logarithmic factors. Building on this lower bound, we give several applications. The first one involves improved results for the security of several combiners in backdoored random oracles (BRO). The second one is an application in distributed computing via connections established by Huang, Pettie, Zhang, and Zhang (SODA 20).
Our proof is built on a structure-vs-pseudorandomness decomposition inspired by Göös, Pitassi and Watson (FOCS 17), and this technique could be of independent interest since it enables a new method to prove communication lower bounds for search problems with many possible solutions. To the best of our knowledge, existing lower-bound techniques do not apply to this setting.
