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

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

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.