Andoni, Alexandr ;
Malkin, Tal ;
Nosatzki, Negev Shekel
Two Party Distribution Testing: Communication and Security
Abstract
We study the problem of discrete distribution testing in the twoparty 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 epsilonfar (in the l_1 distance). This is in contrast to the wellstudied oneparty case, where the tester has unrestricted access to samples of both distributions. Despite being a natural constraint in applications, the twoparty setting has previously evaded attention.
We address two fundamental aspects of the twoparty setting: 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 or epsilonfar from being independent. Our contribution is threefold: 1) We show how to gain communication efficiency given more samples, beyond the informationtheoretic bound on t. The gain is polynomially better than what one would obtain via adapting oneparty algorithms. 2) We prove tightness of our tradeoff for the closeness testing, as well as that the independence testing requires tight Omega(sqrt{m}) communication for unbounded number of samples. These lower bounds are of independent interest as, to the best of our knowledge, these are the first 2party communication lower bounds for testing problems, where the inputs are a set of i.i.d. samples. 3) We define the concept of secure distribution testing, and provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.
BibTeX  Entry
@InProceedings{andoni_et_al:LIPIcs:2019:10591,
author = {Alexandr Andoni and Tal Malkin and Negev Shekel Nosatzki},
title = {{Two Party Distribution Testing: Communication and Security}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {15:115:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10591},
URN = {urn:nbn:de:0030drops105916},
doi = {10.4230/LIPIcs.ICALP.2019.15},
annote = {Keywords: distribution testing, communication complexity, security}
}
04.07.2019
Keywords: 

distribution testing, communication complexity, security 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 