EAGER: Testing Pseudorandom Distributions

EAGER：测试伪随机分布

• 批准号: 1650733
• 负责人: Ronitt Rubinfeld
• 金额: $ 30万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1650733&HistoricalAwards=false
• 关键词: EAGER; Testing; Pseudorandom; Distributions

It is common scientific practice to propose a model which randomly generates combinatorial objects that are intended to be good approximations of data that we see in the real world. Such models include widely studied random graph models, preferential attachment models and small world networks. Since these models are in such widespread use, many analytical algorithms have been proposed to work with data assumed to be generated according to them. This project has the larger goal of giving a methodology for understanding when these hypothesized models accurately describe the actual data. Unfortunately, it can be shown that for these and other related models, testing that the data comes from such a model requires a tremendous number of samples in the worst case. This project studies methods of making the problem more tractable by determining whether the models are "good enough" descriptions of the data: that is, determining whether the actual data yields the same behavior as the data generated by the models, from the point of view of the analytical algorithms being used. The PIs will exploit potential computational limitations of the analytical algorithms to expedite the tasks of testing randomness properties of the actual samples. In technical terms, this project investigates ways of testing the pseudo-randomness of distributions against various specific classes of algorithms and circuits. Connections to the complexity theoretic concepts of derandomization and circuit lower bounds will be explored.The broader impact of this project includes engagement in Computer Science Unplugged activities for elementary school children, MIT PRIMES mathematical research with high school students, participation in activities for promoting women in research, mentoring and education of young researchers, development of new courses, and dissemination of results through publications, surveys, and public lectures.

通常的科学实践是提出一个随机生成组合对象的模型，该模型旨在很好地近似我们在现实世界中看到的数据。这些模型包括被广泛研究的随机图模型、优先依恋模型和小世界网络。由于这些模型被如此广泛地使用，许多分析算法被提出来处理假定根据这些模型生成的数据。这个项目有一个更大的目标，即提供一种方法来理解这些假设模型何时能准确地描述实际数据。不幸的是，可以证明，对于这些模型和其他相关模型，在最坏的情况下，测试数据来自这样一个模型需要大量的样本。该项目研究通过确定模型是否“足够好”地描述数据来使问题更易于处理的方法：也就是说，从所使用的分析算法的角度出发，确定实际数据是否产生与模型生成的数据相同的行为。pi将利用分析算法的潜在计算限制来加快测试实际样本随机性属性的任务。在技术术语中，该项目研究了针对各种特定类别的算法和电路测试分布的伪随机性的方法。将探讨与非随机化和电路下界的复杂性理论概念的联系。该项目的广泛影响包括参与针对小学生的计算机科学不插电活动，与高中生一起进行MIT PRIMES数学研究，参与促进女性参与研究的活动，指导和教育年轻研究人员，开发新课程，以及通过出版物，调查和公开讲座传播结果。

项目成果

Dimension Reduction for Polynomials over Gaussian Space and Applications

高斯空间多项式的降维及其应用

• 发表时间: 2018
• 期刊: Computational Complexity Conference (CCC
• 作者: Ghazi, B.;Kamath, P.;Raghavendra, P.
• 通讯作者: Raghavendra, P.

Decidability of Non-Interactive Simulation of Joint Distributions

联合分布的非交互式模拟的可判定性

• 发表时间: 2016
• 期刊: Annual Symposium on Foundations of Computer Science
• 作者: Ghazi, Badih;Kamath, Pritish;Sudan, Madhu
• 通讯作者: Sudan, Madhu

Set Cover in Sub-linear Time

以亚线性时间设定封面

• 发表时间: 2018
• 期刊: Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Indyk, Piotr;Mahabadi, Sepideh;Rubinfeld, Ronitt;Vakilian, Ali;Yodpinyanee, Anak
• 通讯作者: Yodpinyanee, Anak

Resource-Efficient Common Randomness and Secret-Key Schemes

资源高效的通用随机性和密钥方案

• 发表时间: 2018
• 期刊: Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Ghazi, Badih;Jayram, T.S.
• 通讯作者: Jayram, T.S.

Robust Repeated Auctions under Heterogeneous Buyer Behavior

不同买家行为下的稳健重复拍卖

• 发表时间: 2018
• 期刊: 19th ACM conference on Economics and Computation
• 作者: Agrawal, Shipra;Daskalakis, Constantinos;Mirrokni, Vahab;Sivan, Balasubramanian
• 通讯作者: Sivan, Balasubramanian