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

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

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.