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

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

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.