On the power of conditional samples in distribution testing

DOI10.1145/2422436.2422497zbMath1362.68288arXiv1210.8338MaRDI QIDQ2986902

Eldar Fischer, Sourav Chakraborty, Arie Matsliah, Yonatan Goldhirsh

Publication date: 16 May 2017

Published in: SIAM Journal on Computing, Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.8338

zbMATH Keywords

property testing; statistical approximation; distribution testing; conditional samples

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68W20: Randomized algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)