Two Party Distribution Testing: Communication and Security

By Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki. 2018

15 citations recorded by the source corpus.

We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have $t$ samples from, respectively, distributions $a$ and $b$ over $[n]$, and they need to test whether $a=b$ or $a,b$ are $\epsilon$-far for some fixed $\epsilon>0$. This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions, for which optimal bounds are known for a number of variations. Despite being a natural constraint in applications, the two-party setting has evaded attention so far. We address two fundamental aspects: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other's input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have $t$ samples from distributions $a$ and $b$ respectively, which may be correlated; the question is whether $a,b$ are independent of $\epsilon$-far from being independent. Our contribution is three-fold: 1) Communication: we show how to gain communication efficiency with more samples, beyond the information-theoretic bound on $t$. The gain is polynomially better than what one obtains by adapting standard algorithms. 2) Lower bounds: we prove tightness of our protocols for the closeness testing, and for the independence testing when the number of samples is unbounded. These lower bounds are of independent interest as these are the first 2-party communication lower bounds for testing problems. 3) Security: we define secure distribution testing and argue that it must leak at least some minimal information. We then provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “Recent results in this area have focused on more complicated communication models [53], [54] and, more recently, on the minimum communication requirements for large sample sizes [6], [44].”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “Another recent work Andoni et al. (2018) studies distributed closeness testing in a two party setting where each party has access to samples from one of the two distributions.”
Distributed Signal Detection under Communication Constraints (2020, background): “…Xu and Raginsky, 2017; Han et al., 2018a,b; Barnes et al., 2019; Cai and Wei, 2020; Acharya et al., 2019b,d), while distributed testing of distributions in the ﬁnite sample regime was considered in (Acharya et al., 2019b,d; Andoni et al., 2018; Fischer et al., 2018; Diakonikolas et al., 2019).”