DIMACS Special Focus on Fine-Grained Complexity

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

The traditional goal of complexity theory is to classify problems as computationally tractable (i.e., in P, the class of polynomial-time-computable decision problems) or not. Fine-grained complexity investigates relationships between problems within P using precise reductions that preserve various parameters and this approach aids in comparing relative difficulty. Over nearly a decade, fine-grained complexity has evolved with tools applicable to dynamic graph algorithms, stringology, etc. The proposed Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) Special Focus on Fine-grained Complexity aims to consolidate efforts through workshops, tutorials, and a visitor program. Broader impacts include building a diverse community in theoretical computer science and contributing to various other areas of computer science including computational biology and machine learning. Efforts to broaden participation include a rigorous five-day tutorial on fine-grained complexity for graduate students organized by Amir Abboud and Nick Fisher, support for underrepresented groups in computer science, and making resources publicly available. The DIMACS special focus proposes four workshops, each of which addresses an overarching application area or technique in fine-grained complexity: 1) Algebraic Techniques in Fine-Grained Complexity organized by Josh Alman; 2) Hardness of Approximation in P organized by Karthik C. S.; 3) Fine-Grained Complexity of Graph Problems organized by Thatchaphol Saranurak; and 4) Fine-Grained Complexity of String Problems organized by Elazar Goldenberg. The workshops will bring together researchers from different communities to facilitate the exchange of ideas and work toward developing a set of long-term and short-term goals with respect to the most compelling open problems within the workshop’s theme. 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.