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.