NSF Young Investigator: Small Depth Boolean Circuits and Complexity - Theoretic Cryptography

NSF 青年研究员：小深度布尔电路和复杂性 - 理论密码学

• 批准号: 9257979
• 负责人: Russell Impagliazzo
• 金额: $ 23万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-15 至 1997-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9257979&HistoricalAwards=false
• 关键词: NSF; Young; Investigator; Small; Depth

This award funds continuing investigations into two long-term interests: the complexity of small depth Boolean circuits, and the computational complexity foundations of cryptography. Computational complexity as a field strives to provide a mathematical foundation for computer science by developing techniques to evaluate the inherent difficulty of computational problems. The Boolean circuit seems the most natural and robust concrete model of computational complexity. Much work has gone into developing the theory of circuit complexity in the hope of resolving such questions as P vs. NP. There are strong connections between bounds on circuit depth and issues in the theory of parallel computation, logic (mostly proof theory), learning theory, and the theory of neural nets. Continuing projects in circuit complexity are: establishing links between circuit bounds and Frege proofs; examining the behavior of formulas under random restrictions, (also known as neural nets). Of course, circuit complexity is a dynamic area, and specific projects may change with new results. Work continues on the foundations of cryptography. Recent work in developing the structural complexity of cryptography has been so successful that perhaps all the major, tractable questions in the area have been resolved. Indeed, there seem to be some theoretical roadblocks to further progress in this direction. However, there are several important open questions regarding the relationship between average-case complexity and cryptography, and that between oblivious transfer and secret agreement. More importantly, a large gap remains between theory and practice. Another goal of the project is to develop theoretical tools that will actually lead to implementable cryptosystems, and to handle such questions as virus protection, secure electronic transfer of funds, and such issues as privacy vs. security for electronic mail.

该奖项资助了对两个长期兴趣的持续研究：小深度布尔电路的复杂性和密码学的计算复杂性基础。 计算复杂性作为一个领域，致力于通过开发技术来评估计算问题的固有难度，为计算机科学提供数学基础。 布尔电路似乎是计算复杂性的最自然和最健壮的具体模型。 为了解决诸如P与NP的问题，人们在发展电路复杂性理论方面做了大量工作。 电路深度的界限与并行计算理论、逻辑（主要是证明理论）、学习理论和神经网络理论中的问题之间有很强的联系。 电路复杂性的持续项目是：建立电路边界和弗雷格证明之间的联系;检查随机限制下公式的行为（也称为神经网络）。 当然，电路复杂性是一个动态的领域，具体项目可能会随着新的结果而变化。 密码学的基础工作仍在继续。 最近在发展密码学的结构复杂性方面的工作是如此成功，以至于该领域中所有主要的、易处理的问题都已经解决了。 事实上，在这方面取得进一步进展似乎存在一些理论上的障碍。 然而，关于平均情况复杂度与密码学之间的关系，以及不经意传输与秘密协议之间的关系，还有几个重要的悬而未决的问题。 更重要的是，理论和实践之间仍然存在很大差距。 该项目的另一个目标是开发理论工具， 可实现的密码系统，并处理诸如病毒 保护、安全的电子资金转移等问题 as privacy隐私vs. security安全for electronic电子mail邮件.