RCN: DIMACS/Simons Collaboration on Lower Bounds in Complexity Theory

RCN：DIMACS/Simons 在复杂性理论下限方面的合作

• 批准号: 1836666
• 负责人: Tamra Carpenter
• 金额: $ 49.95万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1836666&HistoricalAwards=false
• 关键词: RCN; DIMACS; Simons; Collaboration; Lower

One of the main goals of theoretical computer science is to understand the computational resources needed to solve a given computational problem. Along with the development of new algorithms and new algorithmic techniques, this involves discovering lower bounds on computational resource requirements. The DIMACS/Simons Collaboration on Lower Bounds in Complexity Theory, funded by this award, will speed up progress on some of the most vexing problems in theoretical computer science by enabling sustained collaboration and intense focus over a period of several years and will strengthen the research community whose work is dedicated to proving lower bounds on computational complexity. The research questions addressed by the project are of profound theoretical interest in and of themselves, and are also motivated by extremely pressing practical problems: for example, the cryptographic protocols that currently underlie the internet-based economy all rely on the unproven computational intractability of problems in the complexity class NP.The project seeks to focus attention on lower bounds because there have been some remarkable recent breakthroughs in proving lower bounds in Boolean circuit complexity, arithmetic circuit complexity, and communication complexity, and on the complexity of data structure access mechanisms. The project begins with an intensive program at the Simons Institute for the Theory of Computing at Berkeley in the fall semester of 2018 and continues with a 2.5-year special focus led by DIMACS at Rutgers that will expand the project to include more people and more topics. By providing opportunities to sustain collaborations and share ideas over a span of years, the RCN contributes to research that strives for a more complete and unified theory of the techniques for proving lower bounds, more powerful abstractions, and ultimately, new breakthroughs in computational lower bounds. This Research Collaboration Network enables expansion of the Fall 2018 Simons program, including additional long-term participants and new activities for graduate students and early-career fellows. The DIMACS special focus includes three workshops (Meta-Complexity, Barriers, and Derandomization; Arithmetic and Boolean Circuit Complexity; and Information-Theoretic Methods in Complexity Theory), a day of tutorials in conjunction with the 2019 Conference on Computational Complexity, a focused working group on Data Structure Lower Bounds, support for the twice-yearly New York Area Theory Day, a robust visitor program, and summer research for undergraduates.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.

理论计算机科学的主要目标之一是了解解决给定计算问题所需的计算资源。沿着新算法和新算法技术的发展，这涉及到发现计算资源需求的下限。由该奖项资助的DIMACS/Simons复杂性理论下限合作将通过在几年内实现持续合作和高度关注来加快理论计算机科学中一些最棘手问题的进展，并将加强致力于证明计算复杂性下限的研究社区。该项目所解决的研究问题本身具有深刻的理论意义，也受到极其紧迫的实际问题的激励：例如，在一个实施例中，目前互联网的加密协议基于经济的所有依赖于复杂性类NP中的问题的未经证明的计算棘手性。该项目寻求将注意力集中在下界上，因为最近在证明布尔电路复杂度、算术电路复杂度和通信复杂度的下界，以及数据结构访问机制的复杂度。该项目始于2018年秋季学期在伯克利分校西蒙斯计算理论研究所的一个密集课程，并继续由罗格斯大学的DIMACS领导的2.5年特别关注，该项目将扩大到包括更多的人和更多的主题。通过提供机会，以维持合作和分享思想，在几年的跨度，RCN有助于研究，争取一个更完整和统一的理论的技术证明下界，更强大的抽象，并最终在计算下界的新突破。这个研究合作网络使2018年秋季西蒙斯计划的扩展，包括额外的长期参与者和研究生和早期职业研究员的新活动。DIMACS特别重点包括三个研讨会元复杂性、障碍和去随机化;算术和布尔电路复杂性;和复杂性理论中的信息理论方法），与2019年计算复杂性会议一起的一天教程，数据结构下限的重点工作组，对每年两次的纽约地区理论日的支持，一个强大的访问者计划，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Deterministic graph coloring in the streaming model

• DOI: 10.1145/3519935.3520016
• 发表时间: 2021-09
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Sepehr Assadi;Andrew Chen;Glenn Sun

Cryptographic hardness under projections for time-bounded Kolmogorov complexity

时限柯尔莫哥洛夫复杂度预测下的密码硬度

• DOI: 10.1016/j.tcs.2022.10.040
• 发表时间: 2022
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Allender, Eric;Gouwar, John;Hirahara, Shuichi;Robelle, Caleb
• 通讯作者: Robelle, Caleb

One-Way Functions and a Conditional Variant of MKTP

单向函数和 MKTP 的条件变体

• DOI: 10.4230/lipics.fsttcs.2021.7
• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Allender, Eric;Cheraghchi, Mahdi;Myrisiotis, Dimitrios;Tirumala, Harsha;Volkovich, Ilya
• 通讯作者: Volkovich, Ilya

Bounded Relativization

有界相对化

• 发表时间: 2023
• 期刊: Leibniz international proceedings in informatics
• 作者: Hirahara, Shuichi;Lu, Zhenjian;Ren, Hanlin
• 通讯作者: Ren, Hanlin