This National Science Foundation project grant of $362,015 supports research into developing more fine-grained algorithms under the Computer and Information Science and Engineering program. The University of California, San Diego will conduct this research from November 2021 to January 2023.
Specifically, the awardee will build a unified theory of designing fast approximation algorithms and study their fine-grained computational hardness. They will develop systematic techniques emphasizing tradeoffs between runtime, approximation quality, randomness, and parallelization. This includes new methods like amnesic dynamic programming and fast matrix multiplication over semirings. The research also analyzes query complexity for machine learning problems and its connections to developing efficient algorithms. Elements will integrate into new courses, with algorithms implemented and methodologies possibly adapted through industry collaboration. The work addresses optimization problems from long-standing open questions to modern applications.