The Sunflower Conjecture, Disjunctive Normal Forms, and Beyond

向日葵猜想、析取范式及其他

• 批准号: 1953928
• 负责人: Shachar Lovett
• 金额: $ 30万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-15 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1953928&HistoricalAwards=false
• 关键词: Sunflower; Conjecture; Disjunctive; Normal; Forms

There is a rich history of symbiosis between computer science and mathematics. This award is aimed at further strengthening this connection, and in particular between the fields of theoretical computer science and combinatorics. This project centers around a fundamental open problem in combinatorics, called the sunflower conjecture. This problem originated in 1960 and is still unanswered, despite having numerous applications in mathematics and in computer science. Recent work by the PI has made significant progress towards resolving the conjecture, and this project is focused on continuing this work. The project provides research training opportunities for graduate students.Concretely, the project explores a correspondence between set systems (also known as hypergraphs) and DNFs (Disjunctive Normal Forms). Building upon recent work by the PI, the project demonstrates how tools used to study DNFs can be instrumental in studying set systems, and proposes a unified and versatile framework to make progress on several well-studied conjectures in mathematics and theoretical computer science about the structure of set systems and DNFs. These also include, beyond the sunflower conjecture and related problems in combinatorics, problems related to DNF compression and the Fourier structure of DNFs.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.

计算机科学与数学之间有着丰富的共生历史。该奖项旨在进一步加强这种联系，尤其是在理论计算机科学和组合学领域之间。该项目围绕组合制剂中的基本开放问题，称为向日葵猜想。这个问题起源于1960年，尽管在数学和计算机科学领域有许多应用，但仍未得到答复。 PI的最新工作在解决猜想方面取得了重大进展，该项目的重点是继续进行这项工作。该项目为研究生提供了研究培训机会。紧密地探索了集合系统（也称为HyperGraphs）和DNF（脱节正常形式）之间的对应关系。在PI的最新工作基础上，该项目展示了如何研究DNF的工具在研究集合系统方面有助于研究，并提出了一个统一和多功能的框架，以在数学和理论计算机科学方面的几个精心研究的猜想中取得进展，涉及设定系统和DNF的结构。这些奖项还包括，除了向日葵的猜想和组合学方面的相关问题之外，与DNF压缩有关的问题以及DNF的傅立叶结构。该奖项反映了NSF的法定任务，并被认为值得通过基金会的知识分子优点和更广泛的影响来通过评估来获得支持。

项目成果

Hypercontractivity on high dimensional expanders

• DOI: 10.1145/3519935.3520040
• 发表时间: 2021-11
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Mitali Bafna;Max Hopkins;T. Kaufman;Shachar Lovett

Fractional Certificates for Bounded Functions

有界函数的分数证明

• 发表时间: 2023
• 期刊: Leibniz international proceedings in informatics
• 作者: Lovett, Shachar;Zhang, Jiapeng
• 通讯作者: Zhang, Jiapeng

Sampling Equilibria: Fast No-Regret Learning in Structured Games

抽样均衡：结构化博弈中的快速无悔学习

• 发表时间: 2023
• 期刊: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Beaglehole, Daniel;Hopkins, Max;Kane, Daniel;Liu, Sihan;Lovett, Shachar
• 通讯作者: Lovett, Shachar

High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games

• DOI: 10.1137/1.9781611977073.47
• 发表时间: 2020-11
• 作者: Mitali Bafna;Max Hopkins;T. Kaufman;Shachar Lovett

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

• DOI: 10.48550/arxiv.2205.00644
• 发表时间: 2022-05
• 作者: J. Gaitonde;Max Hopkins;T. Kaufman;Shachar Lovett;Ruizhe Zhang