Subcube Conditional Samples And Testing Properties Of Probability Distributions

点击翻译按钮获取中文摘要

Experimental results or population data induce a distribution. Inferring information from that distribution is a classical problem in statistics. In computer science, the problem has fundamental applications in big-data analysis, cryptography, machine learning, and formal verification. In the last twenty years, the data dimension got larger and larger, and the sample requirements for even the basic statistical tasks have become practically infeasible.We look at the recently introduced conditional sampling framework for testing joint distributions. While the sample complexity improvements have been intriguing for a handful of problems, developing algorithms for many of the hypothesis testing tasks with implementable sample and memory efficiency is still a major open question.Our vision is to build algorithmic foundations of subcube conditional sample-based hypothesis testing. We shall design algorithms for closeness testing, entropy estimation, and memory-efficiency problems. Using the distribution testing algorithms, we shall then create programs to test the robustness of cryptographic designs against random fault attacks and the correctness of samplers implemented in post-quantum cryptographic implementations.