CAREER: Frontiers of Unconditional Derandomization

计算复杂性理论研究高效计算的能力和局限性。也许现代复杂性理论最引人注目的主题是，当考虑到计算限制时，基本概念获得了新的意义。这些概念的突出例子包括证据、保密、知识、策略、交流、互动、学习-最近甚至还有隐私和公平。这些概念中的每一个都比计算机科学早了几千年，乍一看，它们与计算没有本质上的联系。然而，从复杂性理论的角度来看，它们都获得了全新的维度，甚至催生了全新的领域。这一提议围绕着另一个这样的概念--随机性。随机化算法渗透到计算机科学的理论和实践中，在计算机科学之外，随机性是一种特别神秘的现象，长期以来一直令哲学家、物理学家和数学家着迷和沮丧。本项目的重点是随机性的复杂性理论研究，重点是无条件去随机化，即使用具体的结构来消除某些算法中的随机性需求。(著名的猜想，如P=bpp，假设随机化可以完全免除。然而，在这个方向上，除了少数几个重要的结果外，所有这些结果都使用了未经证实的假设。)这本质上是对计算中的随机性的细粒度研究，重点是简单而自然的函数类，如小宽度分支程序、各种受限类型的电路和公式、半空间及其推广。虽然这些函数类不能涵盖所有多项式时间的计算，但这一领域的结果是少数几个可以在没有未经证明的假设的情况下被证明的结果之一。此外，这些类中的每一个都阐明了高效计算的一个重要方面：小深度电路捕获高度可并行化的计算，小宽度分支程序捕获内存效率高的计算，半空间捕获可线性分离的数据，等等。研究人员将为复杂性理论中的三个试金石函数类-多项式阈值函数、多面体和合取范式的布尔公式-开发新的结构结果，并利用这些结果设计它们的最佳伪随机生成器。对该项目的研究将与详细的教育计划完全结合，该计划将涉及并帮助培养研究生和本科生。除了为博士生提供建议外，这位研究员还将继续通过CURIS(斯坦福大学颇受欢迎的本科生夏季研究实习项目)为本科生提供建议；他将开发一套全面的、为期一年的复杂性理论课程序列；他将在斯坦福大学组织一年一度的青年复杂性理论家研讨会；最后，他计划将他的讲稿出版为一本书。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Computational complexity theory studies the power and limitations of efficient computation. Perhaps the most striking theme of modern complexity theory is the fact that basic notions gain new meanings when computational constraints are taken into consideration. Prominent examples of such notions include proofs, secrecy, knowledge, strategy, communication, interaction, learning---and more recently, even privacy and fairness. Each of these notions predates computer science by millennia, and at first blush, are not intrinsically related to computation. And yet, they have all gained entirely new dimensions, and even spawned entirely new fields, when viewed through the lens of complexity theory. This proposal is centered around another such notion, randomness. Randomized algorithms pervade both the theory and practice of computer science; beyond computer science, randomness is an especially enigmatic phenomenon that has long fascinated and frustrated philosophers, physicists, and mathematicians alike.The focus of this project is on the complexity-theoretic study of randomness, with a focus on unconditional derandomization, i.e., using concrete constructions to eliminate the need for randomness in certain algorithms. (Famous conjectures, such as P=BPP, posit that randomization can be dispensed with entirely. However, all but a few significant results in this direction make use of unproved assumptions.) This is essentially a fine-grained study of randomness in computing, focusing on simple and natural function classes such as small-width branching programs, various restricted types of circuits and formulas, half-spaces and their generalizations. While these function classes do not capture all polynomial-time computation, results in this area are among the few that can be proved without unproved hypotheses. Furthermore, each of these classes illuminates an important aspect of efficient computation: small-depth circuits capture highly parallelizable computation, small-width branching programs capture memory-efficient computation, half-spaces capture linearly-separable data, and so on. The investigator will develop new structural results for three touchstone function classes in complexity theory---polynomial threshold functions, polytopes, and Boolean formulas in conjunctive normal form---and leverage these results in the design of optimal pseudorandom generators for them.Research on this project will be fully integrated with a detailed education plan that will involve and help develop graduate and undergraduate students. In addition to advising Ph.D. students, the investigator will continue advise undergraduates through CURIS, Stanford's popular summer undergraduate research internship program; he will develop a comprehensive, year-long course sequence in complexity theory; he will organize an annual young complexity theorists workshop, to be hosted at Stanford; and finally, he plans to publish his lecture notes as a book.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.