EAGER: AF: New approaches to hardness for circuit minimization

EAGER：AF：电路最小化硬度的新方法

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

The goal of this activity is to understand the structure of complexity classes.  Complexity classes provide the best tool currently available for understanding the computational complexity of real-world computational problems.  Some of these problems are notoriously difficult, but recent progress justifies some optimism that additional useful insight about these complexity classes can be obtained.The Minimum Circuit Size Problem (MCSP) is a well-known example of an apparently-intractable problem in NP that is not widely believed to be NP-complete.  Until now, all of the evidence that has been gathered -- trying to indicate that MCSP is hard to compute -- has followed the same path, invoking the connections between derandomization techniques and cryptographically-secure one-way functions.  This proposal will focus on developing a direct approach to reduce seemingly-hard problems to MCSP, and thereby set the stage for a more thorough understanding of the complexity of MCSP. The research results will be broadly disseminated, both through journal publications as well as through survey articles in various venues. The long-term goals of research in computational complexity, if finally achieved, will have profound impact on society (for instance, by providing firm mathematical underpinnings to public-key cryptography, which currently rests upon many unproven conjectures).

这项活动的目标是理解复杂性类的结构。复杂类提供了当前可用于理解现实世界计算问题的计算复杂性的最佳工具，但最近的进展证明了一些乐观的看法。可以获得关于这些复杂性类别的有用见解。最小电路尺寸问题（MCSP）是 NP 中明显棘手的问题的一个众所周知的例子，到目前为止，所有证据都没有被广泛认为是 NP 完全的。已经收集到的- 试图表明 MCSP 难以计算 - 遵循了相同的路径，调用去随机化技术和加密安全单向函数之间的联系​ 该提案将侧重于开发一种直接方法来减少看似困难的问题。 MCSP，从而为更深入地了解 MCSP 的复杂性奠定了基础。研究结果将通过期刊出版物以及各个场所的调查文章进行广泛传播。复杂度,如果最终实现的目标将对社会产生深远的影响（例如，为公钥密码学提供坚实的基础，而公钥密码学目前依赖于许多未经证实的猜想）。

项目成果

The Minimum Oracle Circuit Size Problem

最小预言机电路尺寸问题

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