November 2024
The Special Focus on Lower Bounds in Computational Complexity cruised to a close late this summer. The special focus was part of the DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity, a formal partnership between DIMACS and the Simons Institute for the Theory of Computing funded by the National Science Foundation (NSF). The NSF-sponsored Collaboration supported activities at both DIMACS and the Simons Institute that were devoted to the study of complexity lower bounds and their implications for determining what is (and is not) efficiently computable.
Computational lower bounds are fundamental laws that establish the minimum amount of a resource (time/memory/communication) required to solve a given problem. They capture the inherent difficulty of a computational task, independent of any specific algorithm. By proving an insurmountably large lower bound on the amount of a resource required to perform a computational task, researchers can show that further search for an efficient algorithm is fruitless. In this way, lower bounds can lead to impossibility results. To prove lower bounds, researchers must develop ways of mathematically reasoning about all resource-bounded algorithms, which makes proving them extremely challenging.
The DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity brought together researchers from different areas of theoretical computer science and related mathematics to develop and extend capabilities for proving computational lower bounds. The Collaboration began with an intensive program at the Simons Institute during the fall semester of 2018, and it continued with a multi-year special focus at DIMACS that spanned the COVID-19 pandemic. The Simons program involved three workshops, a Boot Camp, weekly reading groups, seminars, and 73 people who visited the Simons Institute for an extended period during the program. The large number of researchers brought together by the program generated energetic collaboration and a host of new results and subsequent publications.
The DIMACS Special Focus on Lower Bounds in Computational Complexity launched in 2019 with a cluster of complexity-themed events associated with the annual Computational Complexity Conference (CCC2019), which was hosted by Rutgers and DIMACS. In all, the special focus organized six events—three traditional research workshops and three educationally oriented events—and assisted with local hosting of CCC. These events combined to include more than 425 participants:
- CoSP Workshop and School on Algorithms and Complexity
- DIMACS Day of Complexity Tutorials
- Computational Complexity Conference (CCC)
- DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization
- DIMACS Workshop on Lower Bounds and Frontiers in Data Structures
- DIMACS Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools
- Frontiers in Complexity Theory: A Graduate Workshop
Of special note, the Frontiers in Complexity Theory workshop brought 79 students to DIMACS to learn about some of the most exciting trends in complexity research. The workshop was structured around four “mini workshops,” each consisting of a series of three two-hour tutorial-style lectures guiding participants from foundational ideas to recent breakthroughs in the topic area. The mini workshops were: metacomplexity taught by Rahul Ilango (MIT), algebraic complexity taught by Nutan Limaye (IT University of Copenhagen), derandomization taught by Roei Tell (University of Toronto), and error-correcting codes taught by Swastik Kopparty (University of Toronto). Videos of the lectures at the Frontiers in Complexity Theory workshop, as well as those at other special focus workshops are available from each event’s webpage.
The DIMACS special focus also provided support to 18 longer-term visitors, five of whom were undergraduates participating in the DIMACS Research Experiences for Undergraduates (REU) program. Participants in activities conducted at both DIMACS and the Simons Institute reported many new results, some settling long-standing questions and others setting direction for future research. Over the course of the DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity, authors of more than 100 papers told us that these works benefited from activities of the Collaboration.
Among the visitors was professor Michal Koucký (Charles University), who was at DIMACS for the 2023-2024 academic year. During his visit he co-organized the Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools and, together with collaborators, conducted research that led to an almost linear-size sketching scheme for computing edit distance (improving upon previous quadratic schemes) [1] and a randomized list-labeling algorithm with expected cost of O(log3/2n) per operation, which matches the lower bound up to a poly log log n factor [2].
Graduate student Hanlin Ren (University of Oxford) visited postdoc Lijie Chen (UC Berkeley) with support from the special focus, while they both attended the program on Metacomplexity at the Simons Institute. Their research, conducted with other collaborators, led to breakthroughs that include a pseudodeterministic polynomial-time algorithm for constructing primes that works infinitely-often [3] and near-maximum (2n/n) circuit lower bounds for the complexity classes Σ2E and S2E/1 (overcoming the previous half-exponential lower bounds) [4].
Andrew Chen was an undergraduate student at Cornell University when he participated in the 2021 DIMACS REU program with support from the special focus. Research with his mentor Sepehr Assadi (now at Waterloo) and 2020 REU participant Glenn Sun (then at UCLA), yielded a proof that there exist no deterministic semi-streaming algorithms that can achieve even exp(do(1)) colorings of a graph of maximum degree d. There is a randomized semi-streaming algorithm that can color any graph of max-degree d with (d + 1) colors, so the work of Chen and his collaborators confirms that randomization, in fact, is necessary to achieve this [5].
Printable version of this story: [PDF]
Papers Cited:
[1] Michal Koucký and Michael Saks, Almost Linear Size Edit Distance Sketch, Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024.
[2] Michael A Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, and Michael Saks, Nearly Optimal List Labeling, Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS), 2024.
[3] Lijie Chen, Zhenjian Lu, Igor C. Olivera, Hanlin Ren, and Rahul Santhanam, Polynomial-Time Pseudodeterministic Construction of Primes, Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS), 2023.
[4] Lijie Chen, Shuichi Hirahara, and Hanlin Ren, Symmetric Exponential Time Requires Near-Maximum Circuit Size, Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024.
[5] Sepehr Assadi, Andrew Chen, and Glenn Sun, Deterministic Graph Coloring in the Streaming Model, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022.