New Applications of Error-Correcting Codes in Complexity and Algorithms

点击翻译按钮获取中文摘要

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.