AF: Medium: Computational Complexity Theory and Circuit Complexity

点击翻译按钮获取中文摘要

This award focuses on problems in computational complexity theory, with the goal of clarifying the power and limitations of various important classes of algorithms (known as "complexity classes"). Complexity classes provide the best tools currently available for understanding the computational complexity of real-world computational problems. Part of the award supports a collaboration with researchers at the Czech Academy of Sciences.Kolmogorov complexity measures the amount of "information" in a finite string, and also provides a mathematical definition of what it means for a string to be "random". Although the Kolmogorov complexity of an arbitrary string cannot be computed, there are strong connections between the (non-computable) notion of randomness and questions about the circuit size required to compute various functions. This award will support an investigation into recent indications that computational complexity classes can be characterized in terms of efficient access to the Kolmogorov complexity function, thus possibly opening a new portal for techniques from the theory of computability and algorithmic randomness to be applied in complexity theory. The award will also support an investigation into the limits of computation by arithmetic circuits. (In an arithmetic circuit, data can only be manipulated by arithmetic operations such as addition and multiplication; operations that directly access the individual bits of numeric data are not supported.)The long-term goals of research in computational complexity, if finally achieved, will have profound impact on the society---for instance, by providing firm mathematical underpinnings to public-key cryptography, which currently rests upon many unproven conjectures. This research activity offers concrete plans for incremental progress toward this long-range goal. The award also supports graduate education. As such, it will assist with training new researchers and educators. The research results will be broadly disseminated, not only through journal publication but also through survey articles in various venues.