Foundations of Complexity Theory

复杂性理论解决了解决给定计算问题需要多少资源的问题。 近年来，复杂性理论在许多科学和工程学科中找到了联系和应用。 该项目计划在广泛的领域研究复杂性理论。 主题包括通信复杂性，决策树，量子算法，量子密码学和复杂性理论中的其他基础问题。 我们的目标是深入了解计算的本质，以便可以在任何模型中最有效地执行计算任务。 可以预见的是，各种各样的代数和组合技术将被用来探索这些主题。近年来，两个最有趣的科学发展来自于复杂性理论可以用于密码学的认识，以及量子力学可以用于执行强大的计算。 这些领域的进展引起了广大科学界的兴趣，因为它们的相关性是深远的。 该项目的研究可能会导致这两个领域的进一步重大进展。在更广泛的公共教育领域，首席研究员近年来就复杂性，密码学和量子计算等各种主题发表了许多演讲。 这些讲座中有许多是面向普通观众，通常是本科生。 这些讲座，如果精心设计，可以激发年轻人的求知欲，并发展他们对计算科学的兴趣。 随着这些领域研究的进一步发展，可以预期公众的认识和兴趣将进一步提高，从而有利于加强科学教育。

Complexity theory addresses the question of how much resource is needed to solve a given computational problem. In recent years complexity theory has found connections and applications in many scientific and engineering disciplines. This project plans to investigate complexity theory across a broad front. The topics include communication complexity, decision trees, quantum algorithms, quantum cryptography, and other foundational issues in complexity theory. Te goal is to gain deep insights into the nature of computation, so that one can most effectively perform computational tasks in any model. It is expected that a variety of algebraic and combinatorial techniques will be called upon to explore these topics.Two of the most interesting scientific developments in recent years spring from the realization that complexity theory can be utilized for cryptography, and that quantum mechanics can be used for performing powerful computation. Advances in these fronts have attracted interest from scientific communities at large, as their relevance is far-reaching. The research of this project could lead to substantial further progress in these two areas.In the broader domain of public education, the Principal Investigator has given many speeches in recent years on various topics on complexity, cryptography and quantum computing. Many of these talks are geared toward general audiences and often undergraduate students. These lectures, if thoughtfully designed, can stimulate the intellectual curiosity of young minds and develop their interest in the computing sciences. With further advances of research in these areas, one can expect that public awareness and interest will be further enhanced to the good of a stronger scientific education.