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.