CCRI: Planning: Algorithmically Updating Repository of Reductions in Fine-Grained Complexity

点击翻译按钮获取中文摘要

This project develops a community-maintained central repository for recording reductions between computational problems. This infrastructure enables theoretical computer scientists to keep track of progress and the best known results for each problem. Fine-grained complexity is a recent branch of computational complexity theory where the goal is to understand which computational problems can be solved in linear time (where the time required grows proportional to the problem size), and which fundamentally require quadratic time (where the time grows as the square of the problem size), etc. The basis for this field is reductions, which show how to convert problems of one type into problems of another type, and therefore prove relations between those problem types.By recording reductions and their properties in a machine-understandable form, the project enables algorithmic generation of the best known relationships between problems. These automatically derived reductions can strengthen our knowledge of both algorithms and hardness results, and let people identify gaps in their knowledge and thereby define future research directions. The proposed infrastructure could transform the way research is done in fine-grained complexity, and more broadly, theoretical computer science.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.