2019-06-25-diakonikolas19a.md

abstract	section	title	layout	series	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	publisher	container-title	volume	genre	issued	pdf	extras
We study distribution testing with communication and memory constraints in the following computational models: (1) The {\em one-pass streaming model} where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A {\em distributed model} where the data samples reside at multiple machines and the goal is to minimize the communication cost of the protocol. In both these models, we provide efficient algorithms for uniformity/identity testing (goodness of fit) and closeness testing (two sample testing). Moreover, we show nearly-tight lower bounds on (1) the sample complexity of any one-pass streaming tester for uniformity, subject to the memory constraint, and (2) the communication cost of any uniformity testing protocol, in a restricted “one-pass” model of communication.	contributed	Communication and Memory Efficient Testing of Discrete Distributions	inproceedings	Proceedings of Machine Learning Research	diakonikolas19a	0	Communication and Memory Efficient Testing of Discrete Distributions	1070	1106	1070-1106	1070	false	Diakonikolas, Ilias and Gouleakis, Themis and Kane, Daniel M. and Rao, Sankeerth	given family Ilias Diakonikolas given family Themis Gouleakis given family Daniel M. Kane given family Sankeerth Rao	2019-06-25		PMLR	Proceedings of the Thirty-Second Conference on Learning Theory	99	inproceedings	date-parts 2019 6 25	http://proceedings.mlr.press/v99/diakonikolas19a/diakonikolas19a.pdf