Error-correcting Codes and Computation

Introduction

Error-correcting codes are a method for a redundant representation of data that enables one to recover the original data even in the presence of some noise or corruption. In addition to their wide practical applicability, error-correcting codes are also supported by a rich theory, with connections to diverse disciplines in mathematics, science, and engineering.

Interplay with Computation Theory

A particularly fruitful connection has been the interplay with the theory of computation, where:

1. Computational methods were used for the design of error-correcting codes admitting efficient error-correction algorithms.
2. Such codes were useful for a variety of applications within the theory of computation.

Project Objectives

The current project aims to significantly enhance the aforementioned connections.

Main Objective 1

Our first main objective is to design error-correcting codes that:

• Achieve the best possible information-theoretic trade-off between their redundancy and error-resilience.
• Admit super-fast error-correction algorithms.

Main Objective 2

We further believe that such codes are a powerful tool that can be used for boosting the efficiency of various fundamental computational tasks. Our second main objective is to explore such potential applications.

Potential Applications

We outline a couple of such potential applications within the theory of computation, including:

• Obtaining highly-efficient proof systems.
• Fine-grained inapproximability results.
• Fast derandomization.
• Code-based cryptography with low overhead.

Impact of Goals

The goals we plan to pursue are fundamental and long-standing, and even partial progress on them would be groundbreaking, with theoretical and potentially also practical impact.

Recent Progress

Despite the significant challenge, there has recently been exciting progress towards these goals (including by the PI), and we consequently believe that we are now in a unique position for pursuing these goals.