Subcube Conditional Samples And Testing Properties Of Probability Distributions

子立方条件样本和概率分布的测试属性

• 批准号: EP/Y001680/1
• 负责人: Rishiraj Bhattacharyya
• 金额: $ 20.15万
• 依托单位: University of Birmingham
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FY001680%2F1
• 关键词: Subcube; Conditional; Samples; Testing; Properties

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.

实验结果或人口数据会产生分布。从该分布推断信息是统计学中的一个经典问题。在计算机科学中，该问题在大数据分析、密码学、机器学习和形式验证中具有基础应用。在过去的二十年里，数据维度变得越来越大，甚至基本统计任务的样本要求都变得实际上不可行。我们看看最近引入的用于测试联合分布的条件抽样框架。虽然样本复杂性的改进对于一些问题来说很有趣，但为许多具有可实现的样本和内存效率的假设检验任务开发算法仍然是一个主要的悬而未决的问题。我们的愿景是建立基于子立方条件样本的假设的算法基础测试。我们将设计用于紧密度测试、熵估计和内存效率问题的算法。然后，我们将使用分布测试算法创建程序来测试密码设计针对随机故障攻击的鲁棒性以及在后量子密码实现中实现的采样器的正确性。