AF: Small: Computational Entropy

香农在他1948年创立信息论的论文中引入了“熵”的概念来衡量一个过程中的“随机性”。然而，对于具有有限资源的计算机来说，随机性的数量可能看起来与香农熵非常不同。事实上，“计算熵”的各种度量在计算复杂性和密码学的基础中非常有用。PI和其他人最近的工作引入了计算熵的新度量，增加了我们对新旧计算熵度量的理解，并发现这些度量在密码学和复杂性理论中具有更大的适用性。本项目旨在完善我们对计算熵的理解，利用计算熵寻求统一和最优的密码原语结构，使我们更接近于解决空间边界计算中的随机性的力量，并确定计算熵在计算理论中的新应用。这项研究与PI的教育工作紧密结合。PI继续开发与该项目相关的课程和在线讲义（关于伪随机、密码学和应用代数等主题）。研究生参与研究的各个方面，本科生也定期参与。PI还非常积极地为科学界服务，包括向广大受众传达理论计算机科学研究方向的“视觉掘金”等外展工作。

In his 1948 paper that founded information theory, Shannon introduced a notion of "entropy" to measure the amount of "randomness" in a process. However, to a computer with bounded resources, the amount of randomness can appear to be very different from the Shannon entropy. Indeed, various measures of "computational entropy" have been very useful in computational complexity and the foundations of cryptography. Recent work by the PI and others have introduced new measures of computational entropy, increased our understanding the new and old computational entropy measures, and found greater applicability of the these measures in cryptography and complexity theory.This project aims to refine our understanding of computational entropy, use computational entropy to seek unified and optimal constructions of cryptographic primitives, bring us closer to resolving the power of randomness in space-bounded computation, and identify new applications of computational entropy in the theory of computation.This research is closely integrated with the PI's educational efforts. The PI continues to develop courses and online lecture notes related to the project (on topics such as Pseudorandomness, Cryptography, and Applied Algebra). Graduate students are involved in all aspects of the research, and undergraduates participate regularly as well. The PI is also very active in service to the scientific community, including outreach efforts such as "vision nuggets" that convey research directions in theoretical computer science to a broad audience.