AF: Small: Fundamental Connections in Randomness and Complexity

计算机科学的重大进步来自于找到不同领域之间的联系，然后以不平凡的方式加以利用。在这个项目中，PI寻找新的联系，并计划利用这些和几个随机性和计算复杂性领域中的已知联系。计算复杂性研究哪些问题在计算上难以解决以及为什么，以及时间、空间和随机性等计算资源之间的权衡。随机性在计算机科学中非常有用，并在实践中得到广泛应用。在模拟复杂现象(如天气或经济)时，标准做法是包含随机分量。没有随机性，计算机安全是不可能的。然而，尽管随机性被证明对计算机安全是必要的，但它是否对算法来说是被证明是必要的还不得而知。计算中的一个主要问题是理解随机性的力量，以及它是否真的是算法所必需的。关于这个问题的研究通常集中在两个基本对象上：伪随机生成器和随机性抽取器。伪随机生成器是一种确定性算法，它将少量随机比特扩展为大量伪随机比特，其中使用这些伪随机比特的算法的行为类似于使用完全随机比特的算法。随机性抽取器是一种确定性算法，它将大量低质量的随机性转换为数量较少但仍然很大的高质量随机性。伪随机生成器和随机性抽取器如何与计算问题的下限相关？伪随机生成器和随机性抽取器与密码学有何关系，密码学是计算机安全的数学基础？随机性抽取器与纠错码之间有何关系，纠错码可实现在噪声介质上的可靠传输？代码与机器学习有什么关系？伪随机产生器与计算生物学有何关系？通过发现和利用这些联系，我们可以极大地推进潜在领域的知识，并增加突破的机会。有几个应用领域对社会很重要。了解分子结构可能会影响生物学、医学和药物设计。密码学的改进可能会提高计算机的安全性。机器学习解决了无处不在的大数据。

Major advances in computer science have come from finding connections between different areas and then exploiting them in nontrivial ways. In this project, the PI seeks new connections and plans to capitalize on these and known connections among several areas of randomness and computational complexity. Computational complexity explores which problems are computationally intractable and why, as well as tradeoffs between computational resources such as time, space, and randomness.Randomness is extremely useful in computer science and widely used in practice. When simulating complex phenomena, such as the weather or the economy, it is standard to include random components. Computer security is impossible without randomness. Yet while randomness is provably necessary for computer security, it is not known whether it is provably necessary for algorithms. A major question in computing is to understand the power of randomness and whether it is really necessary for algorithms. Research addressing this question often focuses on two fundamental objects: pseudorandom generators and randomness extractors. A pseudorandom generator is a deterministic algorithm that expands a small number of random bits into a large number of pseudorandom bits, where algorithms using these pseudorandom bits behave similarly to algorithms using perfectly random bits. A randomness extractor is a deterministic algorithm that converts a large amount of low-quality randomness into a smaller, but still large, amount of high-quality randomness.This project has several themes. How do pseudorandom generators and randomness extractors relate to lower bounds for computational problems? How do pseudorandom generators and randomness extractors relate to cryptography, the mathematical foundations of computer security? How do randomness extractors relate to error-correcting codes, which enable reliable transmission over noisy media? How do codes relate to machine learning? How do pseudorandom generators relate to computational biology? By finding and exploiting these connections, we can greatly advance knowledge in the underlying areas and increase the chances of breakthroughs. Several application areas are important to society. Understanding molecular structure could impact biology, medicine, and drug design. Improvements in cryptography could lead to improved computer security. Machine learning addresses the omnipresent big data.