EAGER: Testing Pseudorandom Distributions

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

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.