AF: Medium: Computational Complexity Theory and Circuit Complexity

AF：中：计算复杂性理论和电路复杂性

• 批准号: 1064785
• 负责人: Eric Allender
• 金额: $ 42.68万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-06-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1064785&HistoricalAwards=false
• 关键词: AF; Medium; Computational; Complexity; Theory

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.

该奖项的重点是计算复杂性理论中的问题，目的是阐明各种重要类别算法的功能和局限性（称为“复杂性类别”）。 复杂性类别提供了当前可用的最佳工具，可用于了解现实世界计算问题的计算复杂性。 该奖项的一部分支持与捷克科学院的研究人员的合作。科尔莫格罗夫复杂性测量有限字符串中的“信息”量，并且还提供了数学定义，以了解字符串为“随机”的含义。 尽管无法计算任意字符串的kolmogorov复杂性，但是（不可计算的）随机性概念与计算各种功能所需的电路大小之间存在很强的联系。 该奖项将支持对最近的迹象进行的调查，即可以通过有效访问Kolmogorov复杂性函数来表征计算复杂性类别，从而为从计算性理论和算法随机性中开放了一个新的门户网站，以便于复杂性理论。 该奖项还将支持对算术电路计算限制的调查。 (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. 这项研究活动提供了朝着这个远程目标逐步进步的具体计划。 该奖项还支持研究生教育。 因此，它将有助于培训新的研究人员和教育者。 研究结果将不仅通过期刊出版，而且通过各个场所的调查文章来广泛传播。

项目成果

The Minimum Oracle Circuit Size Problem

• DOI: 10.1007/s00037-016-0124-0
• 发表时间: 2016-02
• 期刊: computational complexity
• 影响因子: 1.4
• 作者: Eric Allender;D. Holden;Valentine Kabanets