New Applications of Error-Correcting Codes in Complexity and Algorithms

《计算复杂性》擅长于提出有关计算本质的具有深远影响的基本问题，但到目前为止，它还没有成功地回答这些问题。为了推动该领域向前发展，必须培养广泛使用的工具和技术，并发明新的工具和技术。该项目旨在显著扩大纠错码的范围，使其成为解决复杂性中的核心问题（以及算法中的一个基本问题）的强大工具。纠错代码是复杂性中一些最深层结果的核心；该领域的最新发展揭示了一些进一步突破的可能途径。PI将按照以下三个重点进行研究：(1)开发具有关键特征的Parvaresh-Vardy代码的泛化-局部可解码性-通常在复杂性应用中被利用，应用于非随机化和周围问题；(2)设计一种真正的纠错码模拟，它具有纠错码定义特征的近似版本——在一个坐标上不同的两个码字在大多数坐标上必须不同——并具体应用于证明复杂度类MA的电路下界；(3)利用纠错码弥合矩阵乘法“近似”和精确算法之间的差距，利用PI及其合作者开发的群论方法获得矩阵乘法的最佳算法。总体目标是围绕纠错代码开发新的工具和技术，同时攻击不同应用领域中动机良好且重要的问题。解决复杂性和算法中的基本问题反过来又增强了我们对高效计算的理解和掌握。

Computational Complexity excels at posing fundamental questions with far-reaching consequences regarding the nature of computation, but so far it has been not nearly as successful at answering them. To propel the field forward, broadly useful tools and techniques must be cultivated, and new ones invented.This project aims to significantly broaden the reach of error-correcting codes as a powerful tool to attack central problems in Complexity (and one fundamental problem in Algorithms). Error-correcting codes lie at the core of some of the deepest results in Complexity; recent developments in the area reveal possible routes to a number of further breakthroughs.The PI will pursue research organized in the following threethrusts: (1) developing a generalization of Parvaresh-Vardy codes possessing a crucial feature -- local decodability -- often exploited in Complexity applications, with applications to derandomization and surrounding problems; (2) devising a real analog of error-correcting codes possessing an approximate version of the defining feature of error-correcting codes -- that two codewords that differ in one coordinate must differ in most coordinates -- with a concrete application to proving circuit lower bounds in the complexity class MA; and (3) utilizing error-correcting codes to bridge the gap between "approximate" and exact algorithms for matrix multiplication, with the intention of obtaining an optimal algorithm for matrix multiplication using a group-theoretic approach developed by the PI and coauthors.The overall goal is to develop new tools and techniques around error-correcting codes, while attacking well-motivated and significant problems in different application domains. Resolving fundamental problems in Complexity and Algorithms in turn enhances our understanding and mastery of efficient computation.