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码的一般化，该Parvaresh-Vardy码具有在复杂性应用中经常利用的关键特征-局部可解码性，应用于去随机化和周围的问题;（2）设计纠错码的真实的模拟，其具有纠错码的定义特征的近似版本--在一个坐标上不同的两个码字在大多数坐标上一定不同--并具体应用于证明复杂性类MA中的电路下界;以及（3）利用纠错码来弥合矩阵乘法的“近似”算法和精确算法之间的差距，其目的是使用一个组来获得用于矩阵乘法的最佳算法，由PI和合著者开发的理论方法。总体目标是围绕纠错码开发新的工具和技术，同时解决不同应用领域中动机良好的重要问题。 解决复杂性和算法中的基本问题反过来又增强了我们对高效计算的理解和掌握。