AF: Small: Computational Complexity Theory and Circuit Complexity

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

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

Some computational problems require more resources than others. But recognizing which computational problems are hard and which are easy turns out to be extremely challenging. It also turns out to be extremely important, in the following sense. Much of our economy relies on secure on-line financial transactions, and public-key cryptography is an essential component of providing on-line security. However, every public-key cryptographic system relies on the existence of some function that is easy to compute and hard to invert (a so-called one-way function). Despite a half-century of concerted effort, it remains unknown if one-way functions exist. Instead, the field of computational complexity theory has succeeded in developing a framework for understanding how various problems relate to each other. This framework consists of a collection of "complexity classes" and notions of "reductions" among computational problems. It is a surprising empirical observation that the overwhelming majority of computational problems that are encountered in practice can have their computational complexity precisely characterized in terms of these classes. That is: two problems are considered to be "equivalent" if each can be reduced to the other, so that an efficient algorithm for one yields an efficient algorithm for the other. Most computational problems that arise in practice turn out to be equivalent in this sense to a "hardest" problem in some complexity class. Thus, understanding the complexity of real-world computational problems boils down to understanding the relationships among various complexity classes.This project seeks to improve our understanding of the relationships among complexity classes by using the approach of "metacomplexity". The focus of complexity theory is to determine how hard problems are. The focus of metacomplexity is to determine how hard it is to determine how hard problems are. The canonical example of a problem in metacomplexity is the Minimum Circuit Size Problem (MCSP): given the truth table of a Boolean function, determine the size of the smallest circuit computing the function. Recent work has shown that seemingly-slight improvements in our understanding of the complexity of MCSP would have dramatic consequences in terms of answering long-standing open questions about the relationships among complexity classes. The project will seek to build on this recent work, in order to establish a clearer picture of how MCSP fits into the framework of complexity classes, among other investigations in computational complexity theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

一些计算问题比其他问题需要更多的资源。 但认识到哪些计算问题是困难的、哪些是简单的却是极具挑战性的。 从以下意义上来说，它也被证明是极其重要的。 我们的经济大部分依赖于安全的在线金融交易，而公钥加密是提供在线安全的重要组成部分。 然而，每个公钥密码系统都依赖于某种易于计算且难以逆的函数（所谓的单向函数）的存在。 尽管经过半个世纪的共同努力，单向函数是否存在仍然未知。 相反，计算复杂性理论领域已经成功地开发了一个框架来理解各种问题如何相互关联。 该框架由计算问题中“复杂性类别”和“简化”概念的集合组成。 令人惊讶的经验观察是，实践中遇到的绝大多数计算问题都可以根据这些类别精确地描述其计算复杂性。 也就是说：如果两个问题都可以简化为另一个问题，则认为两个问题是“等价的”，这样一个问题的有效算法就会为另一个问题产生一个有效的算法。从这个意义上说，实践中出现的大多数计算问题都相当于某些复杂性类别中的“最难”问题。 因此，理解现实世界计算问题的复杂性归结为理解各种复杂性类别之间的关系。该项目旨在通过使用“元复杂性”的方法来提高我们对复杂性类别之间关系的理解。 复杂性理论的重点是确定问题的难度。元复杂性的重点是确定问题的难度有多大。 元复杂性问题的典型示例是最小电路尺寸问题（MCSP）：给定布尔函数的真值表，确定计算该函数的最小电路的尺寸。 最近的工作表明，我们对 MCSP 复杂性的理解看似微小的改进，将在回答有关复杂性类别之间关系的长期悬而未决的问题方面产生巨大的影响。 该项目将寻求以最近的工作为基础，以便更清晰地了解 MCSP 如何适应复杂性类别的框架以及计算复杂性理论的其他研究。该奖项反映了 NSF 的法定使命，并被认为值得支持通过使用基金会的智力优点和更广泛的影响审查标准进行评估。

项目成果

The Non-Hardness of Approximating Circuit Size

近似电路尺寸的非困难性

• DOI: 10.1007/978-3-030-19955-5_2
• 发表时间: 2021-01
• 期刊: Theory of computing systems
• 影响因子: 0.5
• 作者: Allender, Eric;Ilango, Rahul;Vafa, Neekon
• 通讯作者: Vafa, Neekon

Cryptographic hardness under projections for time-bounded Kolmogorov complexity

时限柯尔莫哥洛夫复杂度预测下的密码硬度

• DOI: 10.1016/j.tcs.2022.10.040
• 发表时间: 2022-11
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Allender, Eric;Gouwar, John;Hirahara, Shuichi;Robelle, Caleb
• 通讯作者: Robelle, Caleb

One-Way Functions and a Conditional Variant of MKTP

单向函数和 MKTP 的条件变体

• DOI: 10.4230/lipics.fsttcs.2021.7
• 发表时间: 2021-11
• 期刊: Leibniz international proceedings in informatics
• 作者: Allender, Eric;Cheraghchi, Mahdi;Myrisiotis, Dimitrios;Tirumala, Harsha;Volkovich, Ilya
• 通讯作者: Volkovich, Ilya

Depth-first search in directed planar graphs, revisited

重新审视有向平面图中的深度优先搜索

• DOI: 10.1007/s00236-022-00425-1
• 发表时间: 2022-08
• 期刊: Acta Informatica
• 影响因子: 0.6
• 作者: Allender, Eric;Chauhan, Archit;Datta, Samir
• 通讯作者: Datta, Samir

Depth-First Search in Directed Planar Graphs, Revisited

重新审视有向平面图中的深度优先搜索

• DOI: 10.4230/lipics.mfcs.2021.7
• 发表时间: 2021-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Allender, Eric;Chauhan, Archit;Datta, Samir
• 通讯作者: Datta, Samir