CAREER: Frontiers of Unconditional Derandomization

职业：无条件去随机化的前沿

• 批准号: 1942123
• 负责人: Li-Yang Tan
• 金额: $ 56万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-02-01 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1942123&HistoricalAwards=false
• 关键词: CAREER; Frontiers; Unconditional; Derandomization

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.

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

项目成果

The composition complexity of majority

大多数的组成复杂性

• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Lecomte;Victor;Ramakrishnan, Prasanna;Li-Yang
• 通讯作者: Li-Yang

Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity

简短公告：一种随机高效的大规模并行连接算法

• DOI: 10.1145/3465084.3467951
• 发表时间: 2021
• 期刊: PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
• 作者: Charikar, Moses;Ma, Weiyun;Tan, Li-Yang
• 通讯作者: Tan, Li-Yang

Fooling Polytopes

欺骗多面体

• DOI: 10.1145/3460532
• 发表时间: 2022
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: O’Donnell, Ryan;Servedio, Rocco A.;Tan, Li-Yang
• 通讯作者: Tan, Li-Yang