CAREER: Efficient Fine-grained Algorithms

自从计算机诞生以来，最基本的问题一直是——计算机可以解决哪些问题？哪些问题可以在合理的时间内解决？这带来了多项式时间可解问题的概念，这些问题被认为是有效的，而np困难的问题需要很长时间才能解决。近似算法领域与不可近似性理论一起，研究了哪些np困难问题可以通过允许近似解来有效地解决。然而，这种算法效率的粗略区分——多项式与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.