CAREER: Efficient Fine-grained Algorithms

自从计算诞生以来，最基本的问题就是--计算机能解决什么问题？哪些问题可以在合理的时间内得到解决？这带来了多项式时间可解问题的概念，与NP-Hard问题相比，多项式时间可解问题被认为是有效的，而NP-Hard问题需要非常长的时间才能解决。近似算法领域与不可逼近理论一起，研究哪些NP-Hard问题可以通过允许近似解来有效地解决。然而，这种算法效率的粗略区别--多项式与NP-Hard，在处理当今的大规模数据时是不够的。我们需要更细粒度的算法设计和分析，以精确地确定多项式运行时间的准确指数，并更好地理解何时不可能加速。遗憾的是，除了少数针对特定问题的创新之外，文献中对这类算法的研究还非常缺乏，本项目的目标是建立一个统一的细粒度算法设计理论来研究快速逼近算法及其细粒度硬度。开发强调运行时间、近似性和随机性之间权衡的系统技术，并帮助设计低复杂性的并行算法，将显著改善最新技术的水平。此外，在核心机器学习应用程序的激励下，该项目提出了一种通过经典查询复杂性来提高效率的替代模型。来自经典查询复杂性的工具以前启发了快速算法的开发，反之亦然；PI预计在这个项目中也会发生类似的连接。这项工作的要素将与新的课程相结合，这里开发的许多算法将被实施，PI与行业的密切联系将导致方法论的可能采用。该项目将解决一系列重要的优化问题，从长期悬而未决的问题到具有不同应用的现代问题。它将从加法组合学、傅立叶分析、率失真理论和电路复杂性引入新的工具来分析算法，并建立下界。具体地说，将开发新的通用技术，如遗忘动态规划、半环上的快速矩阵乘积和低次多项式方法来设计细粒度近似算法及其并行算法。时间复杂性可能并不总是衡量效率的主要标准。在许多核心机器学习问题中，量化通过主动查询获得的标记数据量的查询复杂性更为重要。该项目将首次分析基本学习问题的查询复杂性，并探索其与开发快速算法的联系。

Ever since the inception of computation, the fundamental question has been- what problems can be solved by computers? And which ones can be solved in a reasonable time? This brought in the notion of polynomial time solvable problems which are considered efficient vs NP-hard problems which take prohibitively long time to solve. The field of approximation algorithms, along with the theory of inapproximability, deals with which of the NP-hard problems can be solved efficiently by allowing approximate solutions. However, this crude distinction of algorithmic efficiency--polynomial vs NP-hard, is insufficient when handling today's large scale of data. We need a finer-grained design and analysis of algorithms that pinpoints the exact exponent of polynomial running time, and a better understanding of when a speed-up is not possible. Unfortunately, except for a few problem-specific innovations, the study of such algorithms is deeply lacking in the literature.This project targets to build a unified theory of fine-grained algorithm design to study fast approximation algorithms, and their fine-grained hardness. Developing systematic techniques that emphasize on the trade-offs between running time, approximation and randomness, and aid in designing low-complexity parallel algorithms will significantly improve the state of the art. Moreover, motivated by core machine learning applications, the project proposes an alternate model of efficiency via classical query complexity. Tools from classical query complexity have previously inspired development of fast algorithms and vice versa; the PI expects similar connections to happen in this project. Elements of this endeavor will be integrated with new courses, many of the algorithms developed herein will be implemented and the close connection of the PI with industry will result in possible adaptation of methodologies.The project will address a suite of important optimization problems, from long-standing open questions to modern problems with diverse applications. It will introduce fresh tools from additive combinatorics, fourier analysis, rate distortion theory, and circuit complexity for analysis of algorithms, and establishing lower bounds. Specifically, new generic techniques of amnesic dynamic programming, fast matrix-product over semiring, and low-degree polynomial method will be developed to design fine-grained approximation algorithms and their parallel counterparts. Time complexity may not always be the primary measure of efficiency. There are many core machine learning problems where query complexity, that quantifies the amount of labeled data acquired via active querying, is more important. The project will analyze for the first time the query complexity of basic learning problems, and explore its connections to developing fast algorithms.