CAREER: Efficient Fine-grained Algorithms

自从计算机诞生以来，最基本的问题一直是--计算机能解决什么问题？哪些问题可以在合理的时间内解决？这带来了多项式时间可解问题的概念，这些问题被认为是有效的，而NP难题需要花费很长的时间来解决。近似算法领域，沿着不可近似性理论，处理哪些NP难题可以通过允许近似解来有效地解决。然而，这种算法效率的粗略区分-多项式与NP难，在处理今天的大规模数据时是不够的。我们需要对算法进行更细粒度的设计和分析，以确定多项式运行时间的确切指数，并更好地了解何时不可能加速。遗憾的是，除了一些特定问题的创新，这类算法的研究在文献中是非常缺乏的。本项目的目标是建立一个统一的理论细粒度算法设计研究快速近似算法，和他们的细粒度硬度。开发系统的技术，强调运行时间，近似和随机性之间的权衡，并帮助设计低复杂度的并行算法将显着提高最先进的。此外，由核心机器学习应用程序的动机，该项目提出了一种替代模型的效率通过经典的查询复杂性。来自经典查询复杂性的工具以前启发了快速算法的开发，反之亦然; 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.