New Applications of Error-Correcting Codes in Complexity and Algorithms

纠错码在复杂性和算法方面的新应用

• 批准号: 0830787
• 负责人: Christopher Umans
• 金额: $ 37.5万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830787&HistoricalAwards=false
• 关键词: New; Applications; Error; Correcting; Codes

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.

计算复杂性在提出基本问题方面出现了关于计算性质的深远后果的基本问题，但到目前为止，它在回答它们方面并没有那么成功。为了推动该领域的前进，必须培养广泛有用的工具和技术，并发明了新的工具。该项目旨在显着扩大错误校正码的范围，作为攻击复杂性中心问题的有力工具（算法中的一个基本问题）。错误校正的代码位于一些最深层结果的核心。该地区的最新发展揭示了许多进一步突破的可能路线。PI将在以下三分之一中进行组织：（1）制定对Parvaresh-vardy代码的概括，具有至关重要的特征 - 局部解释性 - 通常在复杂性应用中利用，以及对衍生物和周围问题的应用； （2）设计一个具有误差校正代码的真实类似物，该代码具有差异校正代码的定义特征的近似版本 - 在大多数坐标中不同的两个坐标中有不同的代码字必须有所不同），并在复杂性类MA中证明电路下限的具体应用； （3）利用错误校正代码来弥合矩阵乘法的“近似”和精确算法之间的差距，目的是使用PI和COATHORS开发的群体理论方法获得最佳的矩阵乘法算法。在围绕错误的代码和技术范围内，围绕错误的代码和技术进行了较大的攻击，在围绕错误的代码和技术方面进行了攻击。 解决复杂性和算法中的基本问题反过来又增强了我们对有效计算的理解和掌握。